Methods and apparatus for identifying network configurations in an existing network

• US 7,120,680 B1
• Filed: 07/15/2002
• Issued: 10/10/2006
• Est. Priority Date: 07/15/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: O'Connell, Ryan S., Higgins, Joseph W., Ackerley, John F.
• Primary Examiner(s): Dinh, Khanh
• Assistant Examiner(s): TRAN, NGHI V
• Application Number:
  US10/195,282
• Time in Patent Office: 1,548 Days
• Field of Search: 709/220, 709/223, 709/230
• US Class Current: 709/220
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

Mechanisms and techniques operate in a computerized device to provide a network analyzer that identifies a useable network configuration in an existing network configuration. The network analyzer receives a preferred network configuration defining a preferred network topology and analyzes an existing network configuration to produce an existing network topology. The network analyzer then compares the preferred network topology to the existing network topology, for example using a graph matching technique, to identify a useable network configuration within the existing network configuration that most closely supports operation of the preferred network configuration.

Claims

1. A method for identifying a useable network configuration, the method comprising the step of:

receiving a preferred network configuration defining a preferred network topology;

analyzing an existing network configuration to produce an existing network topology;

comparing the preferred network topology to the existing network topology to identify a useable network configuration within the existing network configuration that most closely supports operation of the preferred network configuration, further including applying a graph matching technique to compare the preferred network graph to the existing network graph to identify at least one useable network configuration corresponding to a set of existing interconnected nodes in the existing graph that most closely correspond to preferred nodes in the preferred network graph, the at least one useable network configuration indicating which existing nodes can support operation of the preferred network configuration within the existing network configuration, applying a graph matching technique to compare the preferred network graph to the existing network graph further comprising;

iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics to produce a solution set of usable nodes; and

comparing a configuration characteristic of the solution set of useable nodes to a best match configuration characteristic derived from the preferred network graph to determine if the solution set of useable nodes is a best match solution set of useable nodes, and if so, saving the best match solution set of useable nodes as a useable network configuration;

wherein the step of applying a graph matching technique comprises the step of;

selecting a preferred node from the preferred network graph;

selecting an existing node from the existing network graph;

determining, based on node mapping characteristics, if the existing node matches the preferred node, and if so;

i) creating a mapping between the preferred node and the existing node in a solution set of useable nodes; and

ii) identifying the preferred node and the existing node as mapped nodes;

iii) comparing the solution set of useable nodes using a best solution metric to determine if the solution set of useable nodes is a preferred solution set of useable nodes, and if so, saving the solution set of useable nodes in a set of preferred solution sets of useable nodes;

repeating, in a first repeat sequence, the steps of selecting an existing node and determining if the existing node matches the preferred node for all unmapped existing nodes in the existing network graph; and

repeating, in a second repeat sequence, the steps of selecting a preferred node, selecting an existing node, and repeating in the first repeat sequence for all preferred nodes in the preferred network.

2. The method of claim 1 wherein:

the step of receiving a preferred network configuration defining a preferred network topology comprises the step of producing a preferred network graph of nodes defining the preferred network topology;

the step of analyzing an existing network configuration to produce an existing network topology comprises the step of producing an existing network graph of nodes defining the existing network topology.

3. The method of claim 2 wherein the step of receiving a preferred network configuration defining a preferred network topology comprises the steps of:

receiving a set of compute node identifiers, each compute node identifier identifying a respective compute node to process data in the preferred network configuration;

receiving a set of switch node identifiers, each switch node identifier identifying a respective switch node capable of interconnecting compute nodes identified by respective compute node identifiers in the set of compute node identifiers;

receiving at least one interconnect requirement indicating how at least one compute node is to be connected to at least one switch node; and

wherein the step of producing a preferred network graph of nodes defining the preferred network topology comprises the step of producing at least one preferred network graph defining, according to the at least one interconnect requirement, a possible interconnection between compute nodes identified in the set of compute nodes and switch nodes identified in the set of switch nodes.

4. The method of claim 2 wherein the step of producing a preferred network graph of nodes defining the preferred network topology comprises the step of:

confirming an operational validity of the interconnection between compute nodes and switch nodes defined in the at least one preferred network topology.

5. The method of claim 2 wherein the step of analyzing an existing network configuration to produce an existing network topology comprises the steps of:

querying the existing network configuration to identify a set of existing compute nodes operating within the existing network configuration;

querying the existing network configuration to identify a set of existing switch nodes operating within the existing network configuration; and

for each existing compute node and each existing switch node identified in the existing network configuration, performing the steps of;

identifying existing interconnections to at least one of an existing switch node and an existing compute node operating in the existing network configuration; and

storing the existing interconnections within the existing network topology.

6. The method of claim 2 wherein the step of iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics comprises the step of:

determining if a node type of a preferred network node matches a node type of an existing network node, and so, creating a mapping between the preferred network node and the existing network node within the solution set of useable nodes; and

wherein the step of comparing a configuration characteristic of the solution set of useable nodes to a best match configuration characteristic derived from the preferred network graph comprises the step of;

comparing a number of mapped node links in the solution set of useable nodes to a number of mapped node links in the preferred network graph to determine how closely mapped the solution set of useable nodes is to the preferred network graph.

7. The method of claim 2 wherein the step of iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics comprises the steps of:

selecting a preferred node within the preferred network graph;

selecting an existing node within the existing network graph for which a node mapping characteristic matches the selected preferred node;

detecting that the existing node is associated with an unmapped existing buddy node; and

determining if an unmapped preferred buddy node can be mapped to the unmapped existing buddy node, and if so, mapping the preferred node to the existing node within the solution set of useable nodes and mapping the preferred buddy node to the existing buddy node within the solution set of useable nodes.

8. The method of claim 7 wherein the existing buddy node represents an existing node within the existing network graph that must be mapped in conjunction with the selected existing node that matches a selected preferred node in order to allow the preferred network configuration to operate properly within the existing network configuration.

9. The method of claim 2 wherein the step of iteratively mapping node combinations comprises the step of producing multiple solution sets of useable nodes that are determined to be a best match solution set of useable nodes, each defining a useable network configuration within the existing network configuration that will support operation of the preferred network configuration.

10. The method of claim 9 wherein the step of comparing the preferred network topology to the existing network topology comprises the step of:

identifying useable network configurations of existing nodes in the existing network topology that most closely match node configurations within the preferred network topology.

11. The method of claim 2 wherein the step of comparing the preferred network topology to the existing network topology comprises the step of:

comparing the useable network configuration to the preferred network configuration to identify a set of missing nodes and node interconnections within the preferred network configuration that do not exist within the useable network configuration, the set of missing nodes and node interconnections indicating modifications required to be made to the existing network configuration to support operation of the preferred network configuration.

12. The method of claim 2 wherein the step of comparing the solution set of useable nodes to a best solution metric to determine if the solution set of useable nodes is a preferred solution set of useable nodes comprises the steps of:

calculating a missing link attribute on the solution set of useable nodes, the missing link attribute indicating how many preferred nodes are mapped to existing nodes in the solution set of useable nodes; and

comparing the missing link attribute to a best missing link attribute, the best missing link attribute being associated with a solution set of useable nodes and being as close as possible to a preferred missing link attribute indicating how many links between nodes exist in the preferred network topology.

13. The method of claim 1 wherein the step of receiving a preferred network configuration defining a preferred network topology comprises the step of:

obtaining interconnection relationships between preferred compute nodes and preferred switch nodes defined in the preferred network configuration to produce a preferred network graph of nodes defining the preferred network topology; and

wherein the step of analyzing an existing network configuration to produce an existing network topology comprises the steps of;

querying at least one of a set of existing compute nodes and a set of existing switch nodes operating in the existing network configuration to detect existing interconnection relationships between compute nodes and switch nodes operating in the existing network configuration; and

producing an existing network graph of nodes reflecting the existing interconnection relationships between existing compute nodes and existing switch nodes to define the existing network topology.

14. The method of claim 1 wherein:

the existing network configuration defines a set of compute nodes and switch nodes operating as respective processors over an interconnection fabric within a multi-processor computerized device; and

wherein the useable network configuration identified in the step of comparing identifies an arrangement of interconnected compute nodes in the existing network configuration that are interconnected with the interconnection fabric in a manner that most closely resembles an interconnection of preferred compute nodes in the preferred network configuration.

15. The method of claim 1 wherein the step of comparing comprises the steps of:

creating mappings between preferred nodes within the preferred network topology to existing nodes with the existing network topology to develop a solution set of useable nodes in the existing network configuration;

detecting that an existing node has an associated unmapped existing buddy node in the existing network configuration; and

determining if an unmapped preferred buddy node in the preferred network configuration can be mapped to the unmapped existing buddy node, and if so, creating the mapping between the unmapped preferred buddy node to the existing buddy node within the solution set of useable nodes.

16. A computerized device comprising:

an interface;

a memory;

a processor;

an interconnection mechanism coupling the interface, the memory and the processor;

wherein the memory is encoded with a network analyzer application that when performed by the processor, produces a network analyzer process that causes the computer system to identify a useable network configuration by performing the processing steps of;

receiving, into the memory via the interface, a preferred network configuration defining a preferred network topology;

analyzing an existing network configuration to produce an existing network topology in the memory; and

comparing, in the processor, the preferred network topology to the existing network topology to identify a useable network configuration within the existing network configuration that most closely supports operation of the preferred network configuration such that when the network analyzer process causes the processor to perform the step of comparing the preferred network topology to the existing network topology, the network analyzer process causes the processor to perform the step of applying a graph matching technique to compare the preferred network graph to the existing network graph to identify at least one useable network configuration corresponding to a set of existing interconnected nodes in the existing graph that most closely correspond to preferred nodes in the preferred network graph, the at least one useable network configuration indicating which existing nodes can support operation of the preferred network configuration within the existing network configuration,

wherein when the network analyzer process causes the processor to perform the step of applying a graph matching technique, the network analyzer process causes the processor to perform the step of;

selecting a preferred node from the preferred network graph;

selecting an existing node from the existing network graph;

determining, based on node mapping characteristics, if the existing node matches the preferred node, and if so;

i) creating a mapping between the preferred node and the existing node in a solution set of useable nodes; and

ii) identifying the preferred node and the existing node as mapped nodes;

iii) comparing the solution set of useable nodes using a best solution metric to determine if the solution set of useable nodes is a preferred solution set of useable nodes, and if so, saving the solution set of useable nodes in a set of preferred solution sets of useable nodes;

repeating, in a first repeat sequence, the steps of selecting an existing node and determining if the existing node matches the preferred node for all unmapped existing nodes in the existing network graph; and

repeating, in a second repeat sequence, the steps of selecting a preferred node, selecting an existing node, and repeating in the first repeat sequence for all preferred nodes in the preferred network graph.

17. The computerized device of claim 16 wherein:

when the network analyzer process causes the processor to perform the step of receiving a preferred network configuration defining a preferred network topology, the network analyzer process causes the processor to perform the step of producing a preferred network graph of nodes defining the preferred network topology;

when the network analyzer process causes the processor to perform the step of analyzing an existing network configuration to produce an existing network topology, the network analyzer process causes the processor to perform the step of producing an existing network graph of nodes defining the existing network topology.

18. The computerized device of claim 17 wherein when the network analyzer process causes the processor to perform the step of receiving a preferred network configuration defining a preferred network topology, the network analyzer process causes the processor to perform the steps of:

receiving a set of compute node identifiers, each compute node identifier identifying a respective compute node to process data in the preferred network configuration;

receiving a set of switch node identifiers, each switch node identifier identifying a respective switch node capable of interconnecting compute nodes identified by respective compute node identifiers in the set of compute node identifiers;

receiving at least one interconnect requirement indicating how at least one compute node is to be connected to at least one switch node; and

wherein when the network analyzer process causes the processor to perform the step of producing a preferred network graph of nodes defining the preferred network topology, the network analyzer process causes the processor to perform the step of producing at least one preferred network graph defining, according to the at least one interconnect requirement, a possible interconnection between compute nodes identified in the set of compute nodes and switch nodes identified in the set of switch nodes.

19. The computerized device of claim 17 wherein when the network analyzer process causes the processor to perform the step of producing a preferred network graph of nodes defining the preferred network topology, the network analyzer process causes the processor to perform the step of:

confirming an operational validity of the interconnection between compute nodes and switch nodes defined in the at least one preferred network topology.

20. The computerized device of claim 17 wherein when the network analyzer process causes the processor to perform the step of analyzing an existing network configuration to produce an existing network topology, the network analyzer process causes the processor to perform the step of:

querying the existing network configuration to identify a set of existing compute nodes operating within the existing network configuration;

querying the existing network configuration to identify a set of existing switch nodes operating within the existing network configuration; and

for each existing compute node and each existing switch node identified in the existing network configuration, performing the steps of;

identifying existing interconnections to at least one of an existing switch node and an existing compute node operating in the existing network configuration; and

storing the existing interconnections within the existing network topology.

21. The computerized device of claim 17 wherein when the network analyzer process causes the processor to perform the step of applying a graph matching technique to compare the preferred network graph to the existing network graph, the network analyzer process causes the processor to perform the steps of:

iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics to produce a solution set of usable nodes; and

comparing a configuration characteristic of the solution set of useable nodes to a best match configuration characteristic derived from the preferred network graph to determine if the solution set of useable nodes is a best match solution set of useable nodes, and if so, saving the best match solution set of useable nodes as a useable network configuration.

22. The computerized device of claim 21 wherein when the network analyzer process causes the processor to perform the step of iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics, the network analyzer process causes the processor to perform the step of:

determining if a node type of a preferred network node matches a node type of an existing network node, and so, creating a mapping between the preferred network node and the existing network node within the solution set of useable nodes; and

wherein when the network analyzer process causes the processor to perform the step of comparing a configuration characteristic of the solution set of useable nodes to a best match configuration characteristic derived from the preferred network graph, the network analyzer process causes the processor to perform the step of;

comparing a number of mapped node links in the solution set of useable nodes to a number of mapped node links in the preferred network graph to determine how closely mapped the solution set of useable nodes is to the preferred network graph.

23. The computerized device of claim 21 wherein when the network analyzer process causes the processor to perform the step of iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics, the network analyzer process causes the processor to perform the steps of:

selecting a preferred node within the preferred network graph;

selecting an existing node within the existing network graph for which a node mapping characteristic matches the selected preferred node;

detecting that the existing node is associated with an unmapped existing buddy node; and

determining if an unmapped preferred buddy node can be mapped to the unmapped existing buddy node, and if so, mapping the preferred node to the existing node within the solution set of useable nodes and mapping the preferred buddy node to the existing buddy node within the solution set of useable nodes.

24. The computerized device of claim 23 wherein the existing buddy node represents an existing node within the existing network graph that must be mapped in conjunction with the selected existing node that matches a selected preferred node in order to allow the preferred network configuration to operate properly within the existing network configuration.

25. The computerized device of claim 21 wherein when the network analyzer process causes the processor to perform the step of iteratively mapping node combinations, the network analyzer process causes the processor to perform the step of producing multiple solution sets of useable nodes that are determined to be a best match solution set of useable nodes, each defining a useable network configuration within the existing network configuration that will support operation of the preferred network configuration.

26. The computerized device of claim 25 wherein when the network analyzer process causes the processor to perform the step of comparing the preferred network topology to the existing network topology, the network analyzer process causes the processor to perform the step of:

identifying useable network configurations of existing nodes in the existing network topology that most closely match node configurations within the preferred network topology.

27. The computerized device of claim 21 wherein when the network analyzer process causes the processor to perform the step of comparing the preferred network topology to the existing network topology, the network analyzer process causes the processor to perform the step of:

comparing the useable network configuration to the preferred network configuration to identify a set of missing nodes and node interconnections within the preferred network configuration that do not exist within the useable network configuration, the set of missing nodes and node interconnections indicating modifications required to be made to the existing network configuration to support operation of the preferred network configuration.

28. The computerized device of claim 16 wherein when the network analyzer process causes the processor to perform the step of comparing the solution set of useable nodes to a best solution metric to determine if the solution set of useable nodes is a preferred solution set of useable nodes, the network analyzer process causes the processor to perform the steps of:

calculating a missing link attribute on the solution set of useable nodes, the missing link attribute indicating how many preferred nodes are mapped to existing nodes in the solution set of useable nodes; and

comparing the missing link attribute to a best missing link attribute, the best missing link attribute being associated with a solution set of useable nodes and being as close as possible to a preferred missing link attribute indicating how many links between nodes exist in the preferred network topology.

29. The computerized device of claim 16 wherein when the network analyzer process causes the processor to perform the step of receiving a preferred network configuration defining a preferred network topology the network analyzer process causes the processor to perform the step of:

obtaining interconnection relationships between preferred compute nodes and preferred switch nodes defined in the preferred network configuration to produce a preferred network graph of nodes defining the preferred network topology; and

wherein when the network analyzer process causes the processor to perform the step of analyzing an existing network configuration to produce an existing network topology the network analyzer process causes the processor to perform the steps of;

querying at least one of a set of existing compute nodes and a set of existing switch nodes operating in the existing network configuration to detect existing interconnection relationships between compute nodes and switch nodes operating in the existing network configuration; and

producing an existing network graph of nodes reflecting the existing interconnection relationships between existing compute nodes and existing switch nodes to define the existing network topology.

30. The computerized device of claim 16 wherein:

the existing network configuration defines a set of compute nodes and switch nodes operating as respective processors over an interconnection fabric within a multi-processor computerized device; and

wherein the useable network configuration identified in the step of comparing identifies an arrangement of interconnected compute nodes in the existing network configuration that are interconnected with the interconnection fabric in a manner that most closely resembles an interconnection of preferred compute nodes in the preferred network configuration.

31. The computerized device of claim 16 wherein when the network analyzer process causes the processor to perform the step of comparing, the network analyzer process causes the processor to perform the steps of:

creating mappings between preferred nodes within the preferred network topology to existing nodes with the existing network topology to develop a solution set of useable nodes in the existing network configuration;

detecting that an existing node has an associated unmapped existing buddy node in the existing network configuration; and

determining if an unmapped preferred buddy node in the preferred network configuration can be mapped to the unmapped existing buddy node, and if so, creating the mapping between the unmapped preferred buddy node to the existing buddy node within the solution set of useable nodes.

32. A method for identifying a useable network configuration, the method comprising the steps of:

receiving a preferred network configuration defining a preferred network topology by producing a preferred network graph of nodes defining the preferred network topology;

analyzing an existing network configuration to produce an existing network topology; and

comparing the preferred network topology to the existing network topology to identify a useable network configuration within the existing network configuration that most closely supports operation of the preferred network configuration, further comprising applying a graph matching technique to compare the preferred network graph to the existing network graph to identify at least one useable network configuration corresponding to a set of existing interconnected nodes in the existing graph that most closely correspond to preferred nodes in the preferred network graph, the at least one useable network configuration indicating which existing nodes can support operation of the preferred network configuration within the existing network configuration, the step of receiving a preferred network configuration defining a preferred network topology comprising the steps of;

receiving a set of compute node identifiers, each compute node identifier identifying a respective compute node to process data in the preferred network configuration;

receiving a set of switch node identifiers, each switch node identifier identifying a respective switch node capable of interconnecting compute nodes identified by respective compute node identifiers in the set of compute node identifiers;

receiving at least one interconnect requirement indicating how at least one compute node is to be connected to at least one switch node; and

wherein the step of producing a preferred network graph of nodes defining the preferred network topology comprises the step of producing at least one preferred network graph defining, according to the at least one interconnect requirement, a possible interconnection between compute nodes identified in the set of compute nodes and switch nodes identified in the set of switch nodes;

the step of applying a graph matching technique to compare the preferred network graph to the existing network graph further comprising;

iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics to produce a solution set of usable nodes; and

comparing a configuration characteristic of the solution set of useable nodes to a best match configuration characteristic derived from the preferred network graph to determine if the solution set of useable nodes is a best match solution set of useable nodes, and if so, saving the best match solution set of useable nodes as a useable network configuration;

wherein the step of applying a graph matching technique comprises the step of;

selecting a preferred node from the preferred network graph;

selecting an existing node from the existing network graph;

determining, based on node mapping characteristics, if the existing node matches the preferred node, and if so;

i) creating a mapping between the preferred node and the existing node in a solution set of useable nodes; and

ii) identifying the preferred node and the existing node as mapped nodes;

iii) comparing the solution set of useable nodes using a best solution metric to determine if the solution set of useable nodes is a preferred solution set of useable nodes, and if so, saving the solution set of useable nodes in a set of preferred solution sets of useable nodes;

repeating, in a first repeat sequence, the steps of selecting an existing node and determining if the existing node matches the preferred node for all unmapped existing nodes in the existing network graph; and

repeating, in a second repeat sequence, the steps of selecting a preferred node, selecting an existing node, and repeating in the first repeat sequence for all preferred nodes in the preferred network.

33. The method of claim 32 wherein the step of iteratively mapping node combinations from the preferred network graph and the existing network graph based on corresponding node mapping characteristics comprises the steps of:

selecting a preferred node within the preferred network graph;

selecting an existing node within the existing network graph for which a node mapping characteristic matches the selected preferred node;

detecting that the existing node is associated with an unmapped existing buddy node; and

determining if an unmapped preferred buddy node can be mapped to the unmapped existing buddy node, and if so, mapping the preferred node to the existing node within the solution set of useable nodes and mapping the preferred buddy node to the existing buddy node within the solution set of useable nodes.