Configurations tracking system using transition manager to evaluate votes to determine possible connections between ports in a communications network in accordance with transition tables

• US 5,793,362 A
• Filed: 12/04/1995
• Issued: 08/11/1998
• Est. Priority Date: 12/04/1995
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Vaishnavi, Vick, Matthews, Wallace
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): Luu, Le Hien
• Application Number:
  US08/566,978
• Time in Patent Office: 981 Days
• Field of Search: 395/200.54, 395/200.72, 395/200.53, 379/220, 340/825.06, 370/255, 345/349, 707/266
• US Class Current: 709/224
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04M 3/2254 in networks
• CPC Class Codes: H04Q 2213/13544 modeling or simulation, particularly of networks
• CPC Class Codes: H04Q 2213/13545 monitoring of signaling messages, intelligent network
• CPC Class Codes: H04Q 3/0062 Provisions for network management

Abstract

A network is monitored for reports indicative of a connection state among ports of a communications network. Certain ports are designated as being in a transition, and a transition table is created for each transition. The transition table includes locations that directly relate the connectivity of a first port with respect to a second port, as well as locations that relate the connectivity of other ports. The contents of the transition table are evaluated to determine the likely configuration of the communications network. State machines may be used to resolve conflicting data within the transition table, by providing a likely connection output based upon different entries within the transition table. A voting scheme is used to evaluate the outputs of the state machines and update the transition table when appropriate, and the updated transition table may also be evaluated.

Claims

1. An apparatus for tracking a configuration of a plurality of ports of a communications network, comprising:

an event stream filter having an input that receives a plurality of reports from the communications network, and an output that provides data associated with at least one transition of the communications network;

at least one transition table, each of which corresponds to a respective one of the at least one transition of the communications network; and

a transition manager, having an input that receives data of the at least one transition table, and an output that provides a link list indicative of the configuration of the plurality of ports based upon the data of the at least one transition table;

wherein the transition manager includes a transition analyzer that creates votes regarding a possible connection between a first port and a second port of the communications network based upon the at least one transition table, the transition analyzer evaluating the votes to determine a likelihood of a connection between the first port and the second port.

2. The apparatus of claim 1, wherein the transition manager includes:

a state machine having an input that receives data from locations of a first table of the at least one transition table that directly relates to a first port and a second port of the communications network, and an output that provides an indication of whether the first port is connected to the second port; and

a transition analyzer, having a first input that receives data of the first transition table, a second input that receives the output of the state machine, and an output that represents a likelihood of a connection between the first port and the second port.

3. The apparatus of claim 1, wherein the transition manager includes:

a state machine having an input that receives data from locations of a first table of the at least one transition table that do not directly relate to a first port and a second port of the communications network, and an output that provides an indication of whether the first port is connected to the second port; and

a transition analyzer, having a first input that receives data of the first transition table, a second input that receives the output of the state machine, and an output that represents a likelihood of a connection between the first port and the second port.

4. The apparatus of claim 1, wherein the transition analyzer includes means for updating data within the at least one transition table based upon the votes to provide updated data, the transition analyzer evaluating the updated data to determine the likelihood of a connection between the first port and the second port.

5. The apparatus of claim 1, wherein the transition manager includes a transition table manager having an output that creates a new transition table when the at least one transition table does not include an existing transition table that is associated with a port of the communications network included in one of plurality of reports.

6. The apparatus of claim 1, wherein:

the at least one transition table includes a first transition table associated with a first port included in one of the plurality of reports, and a second transition table associated with a second port included in the one of the plurality of reports; and

the transition manager includes a transition table merger having an output creates a merged transition table by merging the first transition table with the second transition table.

7. The apparatus of claim 1, wherein:

the at least one transition table includes a plurality of locations, each of the plurality of locations containing a state value that represents a connection state of a first port of the communications network with respect to a second port of the communications network; and

each of the plurality of locations is populated with one of at least three states.

8. The apparatus of claim 7, wherein the at least three states includes:

a first state indicative of a confirmed connection between the first port and the second port;

a second state indicative of a confirmed lack of a connection between the first port and the second port; and

at least one third state indicative of an uncertainty with respect to a possible connection between the first port and the second port.

9. The apparatus of claim 1, wherein the transition manager includes a transition timer having an output that triggers initiating a transition analysis of a selected transition by the transition manager following a predetermined amount of time from when a report associated with the selected transition was received by the event stream filter.

10. A method for tracking a configuration of a plurality of ports of a communications network, comprising the steps of:

(a) determining whether any of the plurality of ports are involved in a transition with respect to the configuration of the plurality of ports;

(b) collecting data associated with the transition by receiving a report that includes an indication that a reporting port of the communications network has a particular connection state with respect to a neighbor port of the communications network and entering information from the report into a transition table associated with one of the reporting port and the neighbor port; and

(c) analyzing the data associated with the transition by analyzing the transition table to determine the configuration of the plurality of ports, wherein the step of analyzing includes the steps of;

providing a first number of votes based upon data within the locations of the transition table that directly relate to the reporting port and the neighbor port;

providing a second number of votes based upon data within the locations of the transition table that do not directly relate to the reporting port and the neighbor port; and

evaluating the first number of votes and the second number of votes to determine a likelihood of a connection between the reporting port and the neighbor port.

11. The method of claim 10, wherein the step of analyzing includes determining a likelihood of a connection between the reporting port and the neighbor port based upon data within locations of the transition table that directly relate to the reporting port and the neighbor port.

12. The method of claim 10, wherein the step of analyzing includes determining a likelihood of a connection between the reporting port and the neighbor port based upon location of the transition table that do not directly relate to the reporting port and the neighbor port.

13. The method of claim 10, wherein the step of evaluating includes the steps of:

updating the data within the locations of the transition table that directly relate to the reporting port and the neighbor port based upon the first number of votes and the second number of votes to provide updated data; and

determining the likelihood of a connection between the reporting port and the neighbor port based upon the updated data.

14. The method of claim 10, wherein:

step (b) includes creating a transition table containing the data associated with the transition when a previous transition table associated with at least one of the reporting port and the neighbor port does not previously exist; and

step (c) includes analyzing the transition table.

15. The method of claim 14, wherein step (b) includes creating a transition table having locations populated with one of at least three states including a state indicative of uncertainty.

16. The method of claim 10, wherein:

step (b) includes creating a merged transition table by merging a first transition table associated with the reporting port with a second transition table associated with the neighbor port; and

step (c) includes analyzing the merged transition table.

17. The method of claim 10, wherein the step of receiving the report includes receiving a new neighbor report that includes an indication that a reporting port of the communications network has a connection to a neighbor port of the communications network.

18. The method of claim 10, wherein the step of receiving the report includes receiving a lost neighbor report that includes an indication that a reporting port of the communications network has lost a connection with a neighbor port of the communications network.

19. The method of claim 10, wherein step (c) includes waiting a predetermined amount of time subsequent to step (b) prior to analyzing the data associated with the transition.

20. An apparatus for tracking a configuration of a plurality of ports of a communications network, the apparatus comprising:

first means for determining whether any of the plurality of ports are involved in a transition with respect to the configuration of the plurality of ports;

second means for collecting data associated with the transition by receiving a report that includes an indication that a reporting port of the communications network has a particular connection state with respect to a neighbor port of the communications network and entering information from the report into a transition table associated with one of the reporting port and the neighbor port; and

third means for analyzing the data associated with the transition by analyzing the transition table to determine the configuration of the plurality of ports, the third means including;

means for providing a first number of votes based upon data within the locations of the transition table that directly relate to the reporting port and the neighbor port;

means for providing a second number of votes based upon data within the locations of the transition table that do not directly relate to the reporting port and the neighbor port; and

means for evaluating the first number of votes and the second number of votes to determine a likelihood of a connection between the reporting port and the neighbor port.

21. The apparatus of claim 20, wherein the means for analyzing includes means for determining a likelihood of a connection between the reporting port and the neighbor port based upon data within locations of the transition table that directly relate to the reporting port and the neighbor port.

22. The apparatus of claim 20, wherein the means for analyzing includes means for determining a likelihood of a connection between the reporting port and the neighbor port based upon locations of the transition table that do not directly relate to the reporting port and the neighbor port.

23. The apparatus of claim 20, wherein the means for evaluating includes:

means for updating the data within the locations of the transition table that directly relate to the reporting port and the neighbor port based upon the first number of votes and the second number of votes to provide updated data; and

means for determining the likelihood of a connection between the reporting port and the neighbor port based upon the updated data.

24. The apparatus of claim 20, wherein:

the second means includes means for creating a transition table containing the data associated with the transition when a previous transition table associated with at least one of the reporting port and the neighbor port does not previously exist; and

the third means includes means for analyzing the transition table.

25. The apparatus of claim 24, wherein the second means includes means for creating a transition table having locations populated with one of at least three states including a state indicative of uncertainty.

26. The apparatus of claim 20, wherein:

the second means includes means for creating a merged transition table by merging a first transition table associated with the reporting port with a second transition table associated with the neighbor port; and

the third means includes means for analyzing the merged transition table.

27. The apparatus of claim 20, wherein the report includes an indication that a reporting port of the communications network has a connection to a neighbor port of the communications network.

28. The apparatus of claim 20, wherein the report includes an indication that a reporting port of the communications network has lost a connection with a neighbor port of the communications network.

29. The apparatus of claim 20, further comprising means for triggering the third means a predetermined amount of time subsequent to the second means collecting the data associated with the transition.