Method for efficiently retrieving topology-specific data for point-to-point networks

• US 8,811,232 B2
• Filed: 03/01/2013
• Issued: 08/19/2014
• Est. Priority Date: 10/26/2005
• Status: Active Grant

• Current Assignee: Sanmina-SCI Corporation
• Original Assignee: Memory Integrity LLC
• Inventors: Bemont, James Wesley
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US13/783,190
• Publication Number:
  US 20130182612A1
• Time in Patent Office: 536 Days
• Field of Search: 370/238, 370/255, 370/395.31, 370/401, 370/408
• US Class Current: 370/255
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

Network topology codes are computed and used as keys to retrieve topology-specific information for isomorphic networks.

Claims

1. In one or more computers, a method of providing topology-specific data for a given point-to-point network, comprising:

pre-computing by one or more of the computers and making available topology-specific data for each one of a plurality of selected point-to-point networks;

calculating by one or more of the computers and making available, for each one of the plurality of selected point-to-point networks having a respective unique topology, a respective unique associated topology code that uniquely identifies the topology of that selected point-to-point network, wherein the associated topology code for each selected point-to-point network is calculated by;

applying, to a graph representing the selected point-to-point network, a node-ordering algorithm that produces a set of node orderings;

using the set of node orderings to produce adjacency matrices for the selected point-to-point network;

using the adjacency matrices to produce candidate topology codes; and

selecting, from the candidate topology codes, a topology code with a maximum value as the key for the selected point-to-point network;

calculating by one or more of the computers a topology code for the given point-to-point network;

using the calculated topology code for the given point-to-point network as a key to look up the pre-computed topology-specific data for any of the plurality of selected point-to-point networks for which the associated topology code is identical to the topology code for the given point-to-point network; and

retrieving the looked-up pre-computed topology-specific data for the given point-to-point network.

2. The method of claim 1 wherein the topology-specific data includes an optimal routing matrix.

3. The method of claim 1 wherein the topology-specific data includes performance statistics.

4. The method of claim 1 wherein the topology-specific data is made available by being cached.

5. The method of claim 1 wherein, for each selected point-to-point network, the associated topology code has a number B of significant bits and the selected network has a number N of nodes which are related by the formula B=N(N−

1)/2.

6. The method of claim 1 wherein each calculated topology code contains all information necessary to reconstruct a graph that is isomorphic to all other graphs having the same topology code.

7. The method of claim 1 including testing whether a given point-to-point network and a selected point-to-point network are isomorphic to each other by comparing their topology codes.