Network topology mapper

• US 7,319,677 B2
• Filed: 12/17/2004
• Issued: 01/15/2008
• Est. Priority Date: 12/17/2004
• Status: Expired due to Fees

• Current Assignee: Los Alamos National Security LLC (Government of the United States of America)
• Original Assignee: Los Alamos National Security LLC (Government of the United States of America)
• Inventors: Quist, Daniel A., Gavrilov, Eugene M., Fisk, Michael E.
• Primary Examiner(s): Patel; Ajit
• Application Number:
  US11/016,096
• Publication Number:
  US 20060133297A1
• Time in Patent Office: 1,124 Days
• Field of Search: 370/254, 370/255, 370/256, 370/257, 370/258, 709/220, 709/221
• US Class Current: 370/254
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/18 Loop-free operations

Abstract

A method enables the topology of an acyclic fully propagated network to be discovered. A list of switches that comprise the network is formed and the MAC address cache for each one of the switches is determined. For each pair of switches, from the MAC address caches the remaining switches that see the pair of switches are located. For each pair of switches the remaining switches are determined that see one of the pair of switches on a first port and the second one of the pair of switches on a second port. A list of insiders is formed for every pair of switches. It is determined whether the insider for each pair of switches is a graph edge and adjacent ones of the graph edges are determined. A symmetric adjacency matrix is formed from the graph edges to represent the topology of the data link network.

Claims

1. A method for discovering the topology of a network data link subnet comprising:

(a) forming a list of switches that comprise the network;

(b) determining a MAC address cache for each one of the switches;

(c) forming from the MAC address caches a list of insiders for every pair of switches;

(d) determining whether the insider for each pair of switches is a graph edge;

(e) determining adjacent ones of the graph edges; and

(f) forming a symmetric adjacency matrix from the graph edges to represent the topology of the network.

2. The method of claim 1, wherein forming a list of insiders further comprises:

(g) determining for each pair of switches all remaining switches that see that pair of switches;

(h) forming the list of insiders by determining for each pair of switches the remaining switches that see one of the pair of switches on a first port and the second one of the pair of switches on a second port.

3. The method of claim 1, further comprising

(i) determining connections of the network data link to hosts and routers forming a full network.

4. The method of claim 3, further including:

(j) determining from the MAC address caches each switch having a port that sees a host or a router but does not see any other switch on that port.

5. A method for propagating MAC tables in switches of an acyclical interconnected network comprising:

(a) recovering at least one edge in the interconnected network directly or indirectly connecting first and second switches on first and second ports, respectively;

(b) determining from a MAC cache in the first switch of the edge first vertices seen from the first switch from ports other than the first port;

(c) determining from a MAC cache in the second switch of the edge second vertices seen from the second switch from ports other than the second port;

(d) propagating the first vertices to the MAC cache of the second switch and the second vertices to the MAC cache of the first port;

(e) repeating steps (a) through (d) for all other edges recovered from the interconnected network;

(f) repeating steps (a) through (e) until the MAC tables in the switches are fully propagated.

6. The method of claim 5 further comprising:

(g) forming a list of switches that comprise the network;

(h) determining the MAC address cache for each one of the switches;

(i) forming from the MAC address caches a list of insiders for every pair of switches;

(j) determining whether the insider for each pair of switches is a graph edge;

(k) determining adjacent ones of the graph edges; and

(l) forming a symmetric adjacency matrix from the graph edges to represent the topology of the network.

7. The method of claim 6, wherein forming a list of insiders further comprises:

(m) determining for each pair of switches all remaining switches that see that pair of switches;

(n) forming the list of insiders by determining for each pair of switches the remaining switches that see one of the pair of switches on a first port and the second one of the pair of switches on a second port.

8. The method of claim 7, further comprising

(o) determining the network data link connections to hosts and routers forming a full network.

9. The method of claim 8, further including:

(p) determining from the MAC address caches each switch having a port that sees a host or a router but does not see any other switch on that port.