Automatic prediction of behavior and topology of a network using limited information

Patent metadata

Field	Value
Publication number	US-11032150-B2
Application number	US-201916443121-A
Country	US
Kind code	B2
Filing date	Jun 17, 2019
Priority date	Jun 17, 2019
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

The present disclosure provides a method for automatically predicting a topology of a network comprising a plurality of nodes. The method includes: selecting a path performance metric among a plurality of available metrics; obtaining path performance metrics of selected node pairs among the plurality of nodes; using the obtained path performance metrics to train a machine-learning model to predict the path performance metric for the remaining node pairs; and using the obtained and predicted path performance metrics to construct a topology of the network.

First claim

What is claimed is:

1. A computer-implemented method for automatically predicting a topology of a network comprising a plurality of nodes, the method comprising:
selecting, by a processor, a path performance metric among a plurality of available metrics;
obtaining, by the processor, a value of the selected path performance metric only for each node pair within a selected subset of node pairs among the plurality of nodes;
using, by the processor, the obtained values of the selected path performance metric to train a machine-learning model to predict a value of the selected path performance metric for all node pairs of the plurality of nodes outside the selected subset; and
using, by the processor, the obtained values and the predicted values of the selected path performance metric to construct a topology of the network,
wherein the path performance metric of a given node pair of the selected subset is based on a communication exchanged between nodes of the given node pair, and
wherein node pairs of the selected subset number less than node pairs of the nodes outside the subset,
wherein the machine-learning model is a neural network including a plurality of layers, where each layer includes a plurality of neurons corresponding to an estimated number of links within the network, and
wherein each neuron is associated with a corresponding one of the node pairs of the selected subset, and when the neural network is operated on input data indicating a given node pair of the node pairs outside the selected subset, a given neuron among the neurons indicates a probability that a link associated with the given neuron is present within a path between nodes of the given node pair.

2. The computer-implemented method of claim 1 , wherein the estimated number of links is twice the number of nodes within the plurality.

3. The computer-implemented method of claim 1 , wherein the selected path performance metric indicates a delay between two nodes of a node pair of the nodes outside the selected subset.

4. The computer-implemented method of claim 1 , wherein the selected path performance metric indicates a congestion level associated with a link between two nodes of a node pair of the nodes outside the selected subset.

5. The computer-implemented method of claim 1 , wherein the processor obtains the values of the selected path performance metric by executing an operating system command to send a message to each node of the node pairs of the selected subset.

6. The computer-implemented method of claim 1 , wherein the machine-learning model is trained using the obtained values of the selected path performance metric and at least one additional path performance metric derived from the obtained values of the selected path performance metric.

7. The computer-implemented method of claim 1 , wherein the topology is constructed by comparing each of the obtained and predicted values of the selected path performance metric with a predefined range.

8. The computer-implemented method of claim 7 , wherein the topology includes a link between a node pair associated with a given value among the obtained and predicted values of the selected performance metric when the given value is within the predefined range and excludes the link when the given value is outside the predefined range.

9. A system for automatically predicting a topology of a network comprising a plurality of nodes, the system comprising:
a memory storing a computer program; and
a processor configured to execute the computer program,
wherein the computer program selects a path performance metric among a plurality of available metrics,
obtains a value of the selected path performance metric only for each node pair within a selected subset of node pairs among the plurality of nodes,
uses the obtained values of the selected path performance metric to train a machine-learning model to predict a value of the selected path performance metric for all node pairs of the plurality of nodes outside the selected subset, and
uses the obtained and predicted values of the selected path performance metric to construct a topology of the network,
wherein the path performance metric of a given node pair of the selected subset is based on a communication exchanged between nodes of the given node pair, and
wherein node pairs of the selected subset number less than node pairs of the nodes outside the subset,
wherein the machine-learning model is a neural network including a plurality of layers, where each layer includes a plurality of neurons corresponding to an estimated number of links within the network,
wherein each neuron is associated with a corresponding one of the node pairs of the selected subset, and when the neural network is operated on input data indicating a given node pair of the node pairs outside the selected subset, a given neuron among the neurons indicates a probability that a link associated with the given neuron is present within a path between nodes of the given node pair.

10. The system of claim 9 , wherein the machine-learning model is trained using the obtained values of the selected path performance metric and at least one additional path performance metric derived from the obtained values of the selected path performance metric.

11. The system of claim 9 , wherein the topology is constructed by comparing each of the obtained and predicted values of the selected path performance metric with a predefined range.

12. The system of claim 11 , wherein the topology includes a link between a node pair associated with a given value among the obtained and predicted values of the selected performance metric when the given value is within the predefined range and excludes the link when the given value is outside the predefined range.

13. A computer program product for automatically predicting a topology of a network comprising a plurality of nodes, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor, to perform method steps comprising instructions for:
selecting a path performance metric among a plurality of available metrics;
obtaining a value of the selected path performance metric only for each node pair within a selected subset of node pairs among the plurality of nodes;
using the obtained values of the selected path performance metric to train a machine-learning model to predict a value of the selected path performance metric for all node pairs of the plurality of nodes outside the selected subset; and
using the obtained and predicted values of the selected path performance metric to construct a topology of the network, and
wherein the path performance metric of a given node pair of the selected subset is based on a communication exchanged between nodes of the given node pair, and
wherein node pairs of the selected subset number less than node pairs of the nodes outside the subset,
wherein the machine-learning model is a neural network including a plurality of layers, where each layer includes a plurality of neurons corresponding to an estimated number of links within the network, and
wherein each neuron is associated with a corresponding one of the node pairs of the selected subset, and when the neural network is operated on input data indicating a given node pair of the node pairs outside the selected subset, a given neuron among the neurons indicates a probability that a link associated with the given neuron is present within a path between nodes of the given node pair.

Assignees

• IBM

Inventors

• Ma Liang
• Srivatsa Mudhakar

Classifications

• G06N3/0895

  Weakly supervised learning, e.g. semi-supervised or self-supervised learning · CPC title

• G06N3/0499

  Feedforward networks · CPC title

• G06N3/09

  Supervised learning · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title