Network topology determination by dissecting unitary connections and detecting non-responsive nodes

• US 5,708,772 A
• Filed: 06/07/1995
• Issued: 01/13/1998
• Est. Priority Date: 04/29/1994
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Zeldin, Paul, Raab, Ilan, Tsang, Suk-Lin
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elmore, Stephen C.
• Application Number:
  US08/477,285
• Time in Patent Office: 951 Days
• Field of Search: 395/183.01, 395/183.03, 395/183.13, 364/267, 364/284.4
• US Class Current: 714/25
• CPC Class Codes: H04L 41/044 comprising hierarchical management structures
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/34 Signalling channels for network management communication

Abstract

A computer-implemented method and apparatus for determining a topology of a network. Signals are received from all source hubs in the network, wherein each of the signals contains connection information for the source hubs including destination hubs to which the source hubs are coupled, and a corresponding connection port on the source hubs through which the destination hubs are coupled. The connection information is processed by locating all unitary connections in the connection information and iteratively performing certain steps until there are no more unitary connections in the connection information. Subsequently, if the connection information is not empty and there are additional unitary connections in the connection information, then the foregoing steps are repeated until there are or more unitary connections or the processed connection information is empty. The resolved connection information is then stored for a complete topology. This above topology method and apparatus is also useful in circumstances where certain source hubs are non-responsive to requests for connection information, that is, they are either malfunctioning or are hubs of an unknown or unsupported type. The connection information may be further processed to determine such non-responsive hubs and insert references to unsupported devices in the processed connection information to show these non-responsive devices in the topology.

Claims

1. A computer-implemented method of determining a topology of a network comprising the following steps:

a. receiving a plurality of signals from a plurality of source hubs in said network, each of said plurality of signals containing connection information for said source hubs including information identifying destination hubs to which said source hubs are coupled, and a corresponding connection port on said source hubs through which said destination hubs are coupled;

b. storing said connection information in a table;

c. processing said connection information by locating unitary connections in said table and iteratively performing the following steps until there are no more said unitary connections in said table;

i. selecting a unitary connection from said table, said unitary connection having a particular source hub and a particular destination hub;

ii. determining return connection information in said table which has said particular destination hub as a source hub, and said particular source hub as a destination hub;

iii. storing said unitary connection in a resolved link area;

iv. storing said return connection information in a back link area;

v. removing said unitary connection from said table;

d. removing from said table all connection information that (a) has a destination hub that matches the destination hub of any given connection information in said resolved link area and (b) does not have a source hub that matches the destination hub of said given connection information in said resolved link area;

e. removing from said table all connection information that (a) matches connection information in said back link area and (b) is the only connection information remaining in said table for a particular source hub;

f. if said table is not empty and there are additional unitary connections in said connection information, then returning to said step c; and

g. determining the topology of the network based on the connection information that is stored in said resolved link area and said back link area.

2. The method of claim 1 wherein said hubs comprise network management modules arranged in said topology including unique connections between each of said network management modules.

3. The method of claim 1 wherein said network comprises an ethernet networking system.

4. The method of claim 1 wherein said connection information for each of said plurality of hubs contains a source address and at least one destination address.

5. The method of claim 4 wherein said source address and said at least one destination address comprise internet protocol (IP) addresses.

6. The method of claim 1 wherein said connection port comprises a port and slot combination on said source hub.

7. The method of claim 1 wherein the connection information that is stored in said resolved link area and said back link area constitute resolved connection information, the method further comprising the steps of:

a. determining if said resolved connection information comprises a plurality of said destination hubs for one connection port on one said source hub, and if not, then terminating, otherwise continuing;

b. for each of said plurality of destination hubs for said one connection port;

i. determining whether said connection information includes return connection information from said each destination hub to said source hub, and if not, then removing said connection information for said one connection port from said connection information and terminating;

ii. establishing new connection information by linking said source hub to an unsupported hub, linking said unsupported hub to said each destination hub, and linking said destination hub to said unsupported hub in said connection information; and

iii. removing said connection information from said source hub to said destination hub, and said connection information from said destination hub to said source hub.

8. The method of claim 7 wherein said step of establishing new connection information includes determining whether said unsupported hub in said connection information already exists, and if not, then creating unsupported connection information.

9. The method of claim 8 wherein said step of establishing new connection information includes determining whether said source and said destination hub are in the same segment, and if not, then determining whether bridge connection information exists between said destination and said source, and if not, then establishing said bridge connection information, establishing new connection information by linking said source hub to said bridge connection information, linking said bridge connection information to said each destination hub, and linking said destination hub to said bridge connection information, removing said connection information from said source hub to said destination hub, and removing said connection information from said destination hub to said source hub.

10. A method of determining topology of a network comprising source hubs which each respond with connection information indicating (i) other hubs to which they are coupled through corresponding connection ports and (ii) the corresponding connection ports through which they are coupled to the other hubs, said network including non-responsive hubs in said network, comprising the steps of:

a. determining if connection information for each source hub comprises a plurality of destination hubs for one connection port on said source hub, and if not, then terminating, otherwise continuing;

b. for each of said plurality of destination hubs for said one connection port;

i. determining whether said connection information includes return connection information from a destination hub to said source hub, and if not, then removing said connection information for said one connection port from said connection information and terminating;

ii. establishing new connection information by linking said source hub to an unsupported hub, linking said unsupported hub to said each destination hub, and linking said destination hub to said unsupported hub in said connection information; and

iii. removing said connection information from said source hub to said destination hub, and said connection information from said destination hub to said source hub.

11. An apparatus for determining a topology of a network comprising:

a. receiver circuitry receiving a plurality of signals from a plurality of source hubs in said network, each of said plurality of signals containing connection information for said source hubs including information identifying destination hubs to which said source hubs are coupled, and a corresponding connection port on said source hubs through which said destination hubs are coupled;

b. memory coupled to said receiver circuitry, said connection information being stored in a table in said memory;

c. processing circuitry coupled to said memory, said processing circuitry processing said connection information by

i. locating unitary connections in said table and executing the following operations until there are no more said unitary connections in said connection information;

(A) selecting a unitary connection from said table, said unitary connection having a particular source hub and a particular destination hub;

(B) determining return connection information in said table which has said particular destination hub as a source hub, and said particular source hub as a destination hub;

(C) storing said unitary connection in a resolved link area;

(D) storing said return connection information in a back link area;

(E) removing said unitary connection from said table;

ii. removing from said table all connection information that (a) has a destination hub that matches the destination hub of any given connection information in said resolved link area and (b) does not have a source hub that matches the destination hub of said even connection information in said resolved link area;

iii. removing from said table all connection information that (a) matches connection information in said back link area and (b) is the only connection information remaining in ,said table for a particular source hub;

iv. if said table is not empty and there are additional unitary connections in said connection information, then returning to said step i; and

v. determining the topology of the network based on the connection information that is stored in said resolved link area and said back link area.