Inferring a network topology

• US 10,516,578 B2
• Filed: 03/31/2015
• Issued: 12/24/2019
• Est. Priority Date: 03/31/2015
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Micro Focus LLC (Open Text Corporation)
• Inventors: Fraenkel, Noam, Shaked, Doron, Cohen Harel, Maya
• Primary Examiner(s): Baturay, Alicia
• Application Number:
  US15/558,659
• Publication Number:
  US 20180115465A1
• Time in Patent Office: 1,729 Days
• Field of Search: 709223
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence

Abstract

In a method for inferring a topology of components in a network, at least one operation parameter is provided for each of a plurality of components in a network, and a similarity measure is computed between at least two of said components based on values of said operation parameters. Based on said similarity measure, it is determined whether said two components are topologically connected, wherein said similarity measure is computed in terms of a normalized mutual information between said operation parameters pertaining to said two components.

Claims

1. A method for inferring a topology of components in a network, comprising:

providing at least one operation parameter for each of a plurality of components in a network;

computing a similarity measure between two of said component based on values of said operation parameters; and

determining whether said two components are topologically connected in said network based on said similarity measure;

wherein said similarity measure is computed in terms of a normalized mutual information between said operation parameters pertaining to said two components.

2. The method according to claim 1, wherein said normalized mutual information is obtained by normalizing with a joint entropy of said operation parameters pertaining to said two components.

3. The method according to claim 1, wherein said normalized mutual information is obtained by normalizing over a sum of mutual information, said sum over said components.

4. The method according to claim 1, wherein said normalized mutual information is a weighted normalized mutual information.

5. The method according to claim 4, wherein weights of said weighted normalized mutual information are given in terms of a standard deviation or a median of said normalized mutual information.

6. The method according to claim 1, wherein providing said at least one operation parameter comprises assigning a probability distribution to said operation parameter.

7. The method according to claim 1, wherein said normalized mutual information pertaining to a pair of components (i,j) and operation parameters (k,l) is given as

8. The method according to claim 7, wherein said similarity measure between a pair of components (i,j) is given as

S_i,j:

=Σ

_kΣ

_lw_k,ltr(M_i^k, M_j^l),

wherein w_k,l denote said weights.

9. The method according to claim 8, wherein

w_k,l:

=w_kδ

_k,l,

wherein w_k denotes a set of weights, and δ

_k,l=1 if k=1, and δ

_k,l=0 otherwise.

10. The method according to claim 1, wherein determining whether said two components are topologically connected in said network comprises comparing said similarity measure against a predetermined threshold value.

11. The method according to claim 1, wherein said operation parameters are parameters quantifying a status or operation of said components in said network.

12. The method according to claim 1, wherein said components are computing devices, and said network is a communication network linking said computing devices.

13. The method according to claim 1, further comprising:

generating a topology comprising a plurality of connections between the plurality of components in the network.

14. A system for inferring a topology of components in a network comprising:

a receiving unit to receive at least one operation parameter for each of a plurality of components in a network; and

a computing unit to compute a similarity measure between two of said components based on values of said operation parameters;

wherein said computing unit determines whether said two components are topologically connected in said network by comparing said similarity measure with a pre-determined threshold value; and

wherein said computing unit computes said similarity measure in terms of a weighted and normalized mutual information between said operation parameters pertaining to said two components.

15. The system according to claim 14, wherein said computing unit obtains said weighted and normalized mutual information by normalizing with a joint entropy of said operation parameters pertaining to said two components.

16. A non-transitory computer-readable storage medium, comprising computer-readable instructions to implement a method comprising:

receiving at least one operation parameter for each of a plurality of components in a network;

computing a similarity measure between at least two of said components based on values of said operation parameters; and

determining;

whether said two components are connected in said network by comparing said similarity measure with a threshold value;

wherein said similarity measure is computed in terms of a normalized mutual information between said operation parameters pertaining to said two components.

17. The non-transitory computer-readable storage medium of claim 16, wherein said normalized mutual information is obtained by normalizing with a joint entropy of said operation parameters pertaining to said two components.

18. The non-transitory computer-readable storage medium of claim 16, wherein said normalized mutual information is obtained by normalizing over a sum of mutual information, said sum over said components.

19. The non-transitory computer-readable storage medium of claim 16, wherein said normalized mutual information is a weighted normalized mutual information.

20. The non-transitory computer-readable storage medium of claim 16, comprising instructions to implement a method comprising:

generating a topology comprising a plurality of connections between the plurality of components in the network.