Region guided and change tolerant fast shortest path algorithm and graph preprocessing framework

Patent metadata

Field	Value
Publication number	US-9599483-B2
Application number	US-201514749354-A
Country	US
Kind code	B2
Filing date	Jun 24, 2015
Priority date	Jun 24, 2015
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

A method for region guided and change tolerant fast shortest path determination and graph preprocessing for network management and control. In an embodiment, a method includes partitioning, by a network component, a plurality of network nodes into a plurality of regions, each network node belonging to one of the regions; identifying, by the network component, border nodes for each region, each border node in a region connecting to at least one border node in a connecting region; determining, by the network component, intervals between regions according to the border nodes, each interval comprising a minimum distance and a maximum distance between two regions; determining, by the network component, a path from a source node to a target node according to the intervals.

First claim

What is claimed is:

1. A method in a network component for path determination, comprising:
partitioning, by the network component, a plurality of network nodes into a plurality of regions, each network node belonging to one of the regions;
identifying, by the network component, border nodes for each region, each border node in a region connecting to at least one border node in a connecting region;
determining, by the network component, intervals between regions according to the border nodes, each interval comprising a minimum distance and a maximum distance between border nodes for each pair of regions; and
determining, by the network component, a path from a source node to a target node according to the intervals.

2. The method of claim 1 , further comprising re-determining intervals for one of the regions in response to a change to border nodes within the one of the regions.

3. The method of claim 1 , wherein determining the path from the source node to the target node according to the intervals comprises eliminating search space according to the intervals.

4. The method of claim 1 , wherein the partitioning comprises a two pass process.

5. The method of claim 4 , wherein a first pass comprises grouping nodes such that each node has a substantially equal probability of being grouped with its closest neighbor.

6. The method of claim 4 , wherein a second pass comprises rebalancing the regions.

7. The method of claim 1 , wherein only a portion of the determined path is recalculated in response to a change in a link between nodes.

8. The method of claim 1 , wherein partitioning comprises partitioning the nodes into a hierarchy of groups and subgroups, wherein at least one group comprises a plurality of subgroups, wherein each subgroup comprises a plurality of nodes.

9. The method of claim 1 , wherein the determined path comprises a plurality of sub-paths, wherein only a sub-path within a group or subgroup in which a changed node is located is recalculated in response to the change.

10. The method of claim 9 , wherein the change comprises one of a change in links to other nodes, a failure of a link to another node, an addition of a link to another node, and an addition of the node to the network.

11. The method of claim 9 , wherein the change comprises one of a change to a drivability of a road, addition of a new road, and a change in speed limit on a road, and wherein the nodes are locations where at least two roads intersect.

12. A network component configured for path determination, comprising:
a processor; and
a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to:
partition a plurality of network nodes into a plurality of regions, each network node belonging to one of the regions;
identify border nodes for each region, each border node in a region connecting to at least one border node in a connecting region;
determine intervals between regions according to the border nodes, each interval comprising a minimum distance and a maximum distance between border nodes for each pair of regions; and
determine a path from a source node to a target node according to the intervals.

13. The network component of claim 12 , wherein the programming further comprises instructions to re-determine intervals for one of the regions in response to a change to border nodes within the one of the regions.

14. The network component of claim 12 , wherein the instructions to determine the path from the source node to the target node according to the intervals comprises eliminating search space according to the intervals.

15. The network component of claim 12 , wherein the instructions to partition comprises a two pass process.

16. The network component of claim 15 , wherein a first pass comprises grouping nodes such that each node has a substantially equal probability of being grouped with its closest neighbor.

17. The network component of claim 15 , wherein a second pass comprises rebalancing the regions.

18. The network component of claim 12 , wherein only a portion of the determined path is recalculated in response to a change in a link between nodes.

19. The network component of claim 12 , wherein the instructions to partition comprises instructions to partition the nodes into a hierarchy of groups and subgroups, wherein at least one group comprises a plurality of subgroups, wherein each subgroup comprises a plurality of nodes.

20. The network component of claim 12 , wherein the determined path comprises a plurality of sub-paths, wherein only a sub-path within a group or subgroup in which a changed node is located is recalculated in response to the change.

21. The network component of claim 20 , wherein the change comprises one of a change in links to other nodes, a failure of a link to another node, an addition of a link to another vertex, and an addition of the node to the network.

22. The network component of claim 20 , wherein the change comprises one of a change to a drivability of a road, addition of a new road, and a change in speed limit on a road, and wherein the nodes are locations where at least two roads intersect.

Assignees

• Futurewei Technologies Inc

Inventors

• Ye Feng
• Tian Chen
• Chen Liya

Classifications

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G06F30/18

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• H04L45/46 Primary

  Cluster building · CPC title

• G06F30/392

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• H04L45/04

  Interdomain routing, e.g. hierarchical routing · CPC title