Methods, devices and systems for determining a target path in a network

Patent metadata

Field	Value
Publication number	US-11218403-B2
Application number	US-202016998813-A
Country	US
Kind code	B2
Filing date	Aug 20, 2020
Priority date	Oct 12, 2018
Publication date	Jan 4, 2022
Grant date	Jan 4, 2022

Abstract

Aspects of the subject disclosure may include, for example, embodiments and a method. The method includes iteratively providing messages to each Node Processor. Each Node Processor represents a node of a group of nodes. The iteratively providing of the messages comprises providing first messages. Each first message includes a cost associated with a path of nodes visited by each first message. A selected path is obtained from each node having a lowest cost of a group of common endpoint costs for paths having common endpoints. A next group of messages includes the selected path. The iteratively providing of the messages results in selected paths. Also, the method include determining a target path from a remaining path. Other embodiments are disclosed.

First claim

What is claimed is:

1. A method, comprising:
iteratively providing, from a message handler of a processing system including a processor, messages to each of a group of node processors of the processing system, wherein each of the group of node processors represents a node of a group of nodes, wherein the iteratively providing of the messages comprises:
providing, by the message handler to a node bus, a group of first messages, wherein each first message of the group of first messages includes a cost associated with a path of nodes visited by the each first message;
obtaining, by the message handler, from each of the group of node processors, a selected path associated with a lowest cost of a group of common endpoint costs for paths having common endpoints among a portion of the group of first messages; and
providing, by the processing system, a next group of messages that includes the selected path, wherein the iteratively providing of the messages results in a plurality of selected paths; and

responsive to the iteratively providing of the messages, determining, by the message handler, a target path that is a remaining path of the plurality of selected paths, wherein the remaining path is identified from the iteratively providing of the messages, and wherein the target path is through each node of the group of nodes.

2. The method of claim 1 , further comprising determining, by the processing system, an existence of a complete path.

3. The method of claim 1 , wherein the target path is a complete shortest path.

4. The method of claim 1 , wherein the group of nodes further comprises a source node, an intermediate node, and a destination node, the intermediate node being situated, with respect to the target path between the source node and the destination node, and wherein the target path is a shortest path connecting at least the source node, the intermediate node, and the destination node.

5. The method of claim 1 , wherein each of the paths having common endpoints traverses a same subgroup of the group of nodes.

6. The method of claim 1 , wherein the lowest cost is associated with a first path from the paths having common endpoints, wherein an identifying of the lowest cost from among the group of common endpoint costs comprises:
identifying, by each of the group of node processors, a next higher cost from among the group of common endpoint costs, wherein the next higher cost is associated with a second path from the paths having common endpoints;
comparing, by each of the group of node processors, the lowest cost to the next higher cost; and
determining, by each of the group of node processors, the lowest cost is lower than the next higher cost.

7. The method of claim 1 , wherein the obtaining of the selected path associated with the lowest cost further comprises identifying, by each of the group of node processors, the selected path and eliminating one or more pruned paths, wherein the cost is one of time, distance, monetary cost, available bandwidth, latency, throughput, risk, or probability of success.

8. A device, comprising:
a processing system including a processor, a group of node processors, an administration processor, and a message handler, wherein each of the group of node processors represents a node of a group of nodes; and
a memory that stores executable instructions that, when executed by the processing system, facilitates performance of operations, the operations comprising:
iteratively providing messages to each of the group of node processors, wherein the iteratively providing of the messages comprises:
providing a group of first messages by the message handler to a node bus, wherein each first message of the group of first messages includes a cost associated with a path of nodes visited by the each first message;
obtaining from each of the group of node processors a selected path associated with a lowest cost of a group of common endpoint costs for paths having common endpoints among a portion of the group of first messages; and
providing a next group of messages that includes the selected path, wherein the iteratively providing of the messages results in a plurality of selected paths; and

responsive to the iteratively providing of the messages, determining a target path that is a remaining path of the plurality of selected paths, wherein the remaining path is identified from the iteratively providing of the messages, wherein the target path is through each node of the group of nodes.

9. The device of claim 8 , wherein the target path is a complete path.

10. The device of claim 8 , wherein the target path is a complete shortest path.

11. The device of claim 8 , wherein each of the paths having common endpoints traverses a same subgroup of the group of nodes.

12. The device of claim 8 , wherein the lowest cost is associated with a first path from the paths having common endpoints, wherein an identifying of the lowest cost from among the group of common endpoint costs further comprises:
identifying by each of the group of node processors a next higher cost from among the group of common endpoint costs, wherein the next higher cost is associated with a second path from the paths having common endpoints;
comparing by each of the group of node processors the lowest cost to the next higher cost; and
determining by each of the group of node processors the lowest cost is lower than the next higher cost.

13. The device of claim 8 , wherein the cost is one of time, distance, monetary cost, available bandwidth, latency, throughput, risk or probability of success.

14. A non-transitory, machine-readable medium, comprising executable instructions that, when executed by a processing system including a processor, a group of node processors, an administration processor, and a message handler, wherein each of the group of node processors represents a node of a group of nodes, facilitate performance of operations, the operations comprising:
iteratively providing messages to each of the group of node processors, wherein the iteratively providing of the messages comprises:
providing a group of first messages by the message handler to a node bus, wherein each first message of the group of first messages includes a quantifiable metric associated with a path of nodes visited by the each first message;
identifying by each of the group of node processors a selected path associated with a lowest quantifiable metric of a group of common endpoint quantifiable metrics for paths having common endpoints among a portion of the group of first messages; and
providing a next group of messages that includes the selected path, wherein the iteratively providing of the messages results in a plurality of selected paths; and

responsive to the iteratively providing of the messages, determining a target path that is a remaining path of the plurality of selected paths, wherein the remaining path is identified from the iteratively providing of the messages, wherein the target path is through each node of the group of nodes.

15. The non-transitory, machine-readable medium of claim 14 , wherein the target path is a complete path.

16. The non-transitory, machine-readable medium of claim 14 , wherein the target path is a complete shortest path.

17. The non-transitory, machine-readable medium of claim 14 , wherein the target path is a shortest path.

18. The non-transitory, machine-readable medium of claim 14 , wherein the quantifiable metric is one of time, distance, monetary cost, available bandwidth, latency, throughput, risk or a probability of success.

Assignees

• At & T Ip I Lp
• At & T Mobility Ii Llc

Inventors

• Meredith Sheldon Kent
• Cottrill William
• Meredith Zachary

Classifications

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L45/08

  Learning-based routing, e.g. using neural networks or artificial intelligence · CPC title

• H04L45/124

  using a combination of metrics · CPC title