Methods, systems and computer program products for finding network segment paths

• US 6,873,619 B1
• Filed: 05/16/2000
• Issued: 03/29/2005
• Est. Priority Date: 05/16/2000
• Status: Expired due to Term

• Current Assignee: Tavve Software Co.
• Original Assignee: Tavve Software Co.
• Inventors: Edwards, Anthony Van Vechten
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Wong, Blanche
• Application Number:
  US09/571,478
• Time in Patent Office: 1,778 Days
• Field of Search: 370/392, 370/401, 370/400, 370/389, 370/351, 370/252
• US Class Current: 370/392
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

Methods, systems and computer program products are provided which may provide network segment path information on a communication network connecting two devices which includes not only devices, such as routers, providing layer three information, but also devices within a subnet, such as a bridge or switch, that maintain layer two information instead of layer three information in their address tables. A link layer data base supporting identification of the bridge/switch devices may be generated and updated automatically by queries to the bridge/switch devices on supported networks and active traffic generation may be used to provide up to date information from the bridge/switch devices. The network segment path information in turn may be used to support root cause analysis of faults on the network.

Claims

1. A method for finding a network segment path for a communication on a communication network supporting Internet protocol (IP) communications, the method comprising:

obtaining link layer information from at least one connecting node on the communication network that does not use layer three Internet protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol; and

determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three Internet protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol.

2. The method of claim 1 wherein the at least one connecting node is a bridge/switch.

3. The method of claim 2 wherein obtaining link layer information further comprises obtaining an identification of the plurality of devices from the bridge/switch.

4. The method of claim 3 wherein obtaining an identification further comprises obtaining a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices.

5. The method of claim 4 wherein obtaining a MAC address further comprises storing obtained MAC addresses and associated connecting port numbers along with an identification of the bridge/switch and respective ones of the plurality of devices as records in a link layer data base.

6. The method of claim 5 wherein storing obtained MAC addresses further comprises time stamping the records and wherein obtaining a MAC address further comprises aging out records in the link layer data base.

7. A method for finding a network segment path for a communication on a communication network comprising:

obtaining link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch based on the Internet protocol, including;

obtaining a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices to provide records;

time stamping the records;

storing the records in a link layer data base; and

aging out records in the link layer data base;

determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the at least one connecting node; and

wherein aging out records comprises;

detecting duplicate records and deleting an older one of detected duplicate records;

detecting conflicts between records indicating movement of at least one of the bridge/switch and one of the plurality of devices; and

deleting records associated with a detected conflict.

8. The method of claim 7 wherein detecting conflicts between records indicating movement further comprises detecting connection of one of the plurality of devices to a plurality of bridge/switches having the same root cost to detect movement of the one of the plurality of devices and wherein deleting records associated with a detected conflict comprises:

deleting all records associated with a moved bridge/switch; and

deleting records associated with the one of the plurality of devices having a time stamp older than at least one other record associated with the one of the plurality of devices.

9. A method for finding a network segment path for a communication on a communication network comprising:

obtaining link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch, including obtaining a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices; and

determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

wherein the plurality of devices and the bridge/switch are on a subnet and wherein obtaining a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices is preceded by initiating communications traffic by the plurality of devices on the subnet.

10. The method of claim 9 wherein obtaining a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices comprises iteratively querying the bridge/switch for next entries in an address table of the bridge/switch using MIB commands until all entries in the address table have been obtained.

11. The method of claim 10 wherein iteratively querying the bridge/switch for next entries further comprises initiating communications traffic by the plurality of devices on the subnet if a specified time is exceeded before all entries in the address table have been obtained.

12. A method for finding a network segment path for a communication on a communication network comprising:

obtaining link layer information from at least one connecting node on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the at least one connecting node; and

determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the at least one connecting node; and

wherein the communication is between a first device and a second device and wherein determining the network segment path for a communication on the communication network comprises;

determining a network path between the first device and the second device;

identifying subnets in the network path; and

determining a subnet path for each of the identified subnets in the network path using a link layer data base.

13. The method of claim 12 wherein identifying subnets in the network path further comprises identifying a first endpoint and a second endpoint in the network path for each subnet in the network path.

14. The method of claim 13 wherein determining a subnet path further comprises the following executed for each subnet:

finding a first path from the first endpoint to a root bridge/switch of the subnet using the link layer data base;

finding a second path from the second endpoint to the root bridge/switch of the subnet using the link layer data base;

removing non-utilized common nodes of the first path and the second path; and

connecting the first path and the second path at a common node.

15. The method of claim 14 wherein connecting the first path and the second path at a common node is preceded by determining an associated port number for each node along the first path and the second path from the link layer data base.

16. The method of claim 14 wherein finding a first path further comprises:

identifying bridges/switches associated with the first endpoint in the link layer data base;

ordering the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.

17. The method of claim 16 wherein ordering the identified bridges/switches is preceded by identifying in the link layer data base additional bridges/switches associated with the identified bridges/switches and wherein ordering the identified bridges/switches further comprises ordering the identified bridges/switches associated with the first endpoint and the additional bridges/switches in root cost order from highest to lowest to provide the first path.

18. The method of claim 17 wherein finding a second path further comprises:

identifying second path bridges/switches associated with the second endpoint in the link layer data base;

ordering the identified second path bridges/switches associated with the second endpoint in root cost order from highest to lowest to provide the second path.

19. The method of claim 18 wherein ordering the identified second path bridges/switches is preceded by identifying in the link layer data base additional bridges/switches associated with the identified second path bridges/switches and wherein ordering the identified second path bridges/switches further comprises ordering the identified bridges/switches associated with the second endpoint and the additional second path bridges/switches in root cost order from highest to lowest to provide the second path.

20. The method of claim 19 wherein determining a network path between the first device and the second device comprises executing a SNMP findroute operation.

21. A method for determining a path between a first endpoint and a second endpoint on a subnet comprising:

finding a first path from the first endpoint to a root bridge/switch of the subnet using a link layer data base;

finding a second path from the second endpoint to the root bridge/switch of the subnet using the link layer data base;

removing non-utilized common nodes of the first path and the second path; and

connecting the first path and the second path at a common node.

22. The method of claim 21 wherein the link layer data base comprises link layer information obtained from at least one bridge/switch on the subnet that does not use layer three protocol information to process communications from a plurality of devices passing through the at least one bridge/subnet.

23. The method of claim 22 wherein connecting the first path and the second path at a common node is preceded by determining an associated port number for each node along the first path and the second path from the link layer data base.

24. The method of claim 22 wherein finding a first path further comprises:

identifying bridges/switches associated with the first endpoint in the link layer data base;

ordering the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.

25. The method of claim 24 wherein ordering the identified bridges/switches is preceded by identifying in the link layer data base additional bridges/switches associated with the identified bridges/switches and wherein ordering the identified bridges/switches further comprises ordering the identified bridges/switches associated with the first endpoint and the additional bridges/switches in root cost order from highest to lowest to provide the first path.

26. The method of claim 24 wherein finding a second path further comprises:

identifying second path bridges/switches associated with the second endpoint in the link layer data base;

ordering the identified second path bridges/switches associated with the second endpoint in root cost order from highest to lowest to provide the second path.

27. The method of claim 26 wherein ordering the identified bridges/switches is preceded by identifying in the link layer data base additional bridges/switches associated with the identified second path bridges/switches and wherein ordering the identified second path bridges/switches further comprises ordering the identified bridges/switches associated with the second endpoint and the additional second path bridges/switches in root cost order from highest to lowest to provide the second path.

28. A system for finding a network segment path for a communication on a communication network supporting Internet protocol (IP) communications, the method comprising:

means for obtaining link layer information from at least one connecting node on the communication network that does not use layer three Internet protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol; and

means for determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three Internet protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol.

29. The system of claim 28 wherein the at least one connecting node is a bridge/switch.

30. The system of claim 29 wherein the means for obtaining link layer information further comprises means for obtaining an identification of the plurality of devices from the bridge/switch, the identification including a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices.

31. The system of claim 30 further comprising means for storing obtained MAC addresses and associated connecting port numbers along with an identification of the bridge/switch and the respective ones of the plurality of devices as records in a link layer data base.

32. The system of claim 31 wherein the means for storing further comprises means for time stamping the records and wherein means for obtaining link layer information further comprises means for aging out records in the link layer data base.

33. A system for finding a network segment path for a communication on a communication network, comprising:

means for obtaining link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch, the means for obtaining link layer information including means for obtaining an identification of the plurality of devices from the bridge/switch, the identification including a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices; and

means for determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

wherein the means for obtaining an identification further comprises means for iteratively querying the bridge/switch for next entries in an address table of the bridge/switch using MIB commands until all entries in the address table have been obtained.

34. The system of claim 33 wherein the means for iteratively querying the bridge/switch for next entries further comprises means for initiating communications traffic by the plurality of devices on the subnet if a specified time is exceeded before all entries in the address table have been obtained.

35. A system for finding a network segment path for a communication on a communication network, comprising:

means for obtaining link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

means for determining the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

wherein the communication is between a first device and a second device and wherein the means for determining the network segment path for a communication over the communication network comprises;

means for determining a network path between the first device and the second device;

means for identifying subnets in the network path; and

means for determining a subnet path for each of the identified subnets in the network path using a link layer data base.

36. The system of claim 35 wherein the means for identifying subnets in the network path further comprises means for identifying a first endpoint and a second endpoint in the network path for each subnet in the network path and wherein the means for determining a subnet path further comprises:

means for finding a first path from the first endpoint to a root bridge/switch of a subnet using the link layer data base;

means for finding a second path from the second endpoint to the root bridge/switch of the subnet using the link layer data base;

means for removing non-utilized common nodes of the first path and the second path; and

means for connecting the first path and the second path at a common node.

37. The system of claim 36 wherein the means for finding a first path further comprises:

means for identifying bridges/switches associated with the first endpoint in the link layer data base;

means for ordering the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.

38. The system of claim 37 further comprising means for identifying in the link layer data base additional bridges/switches associated with the identified bridges/switches and wherein the means for ordering the identified bridges/switches further comprises means for ordering the identified bridges/switches associated with the first endpoint and the additional bridges/switches in root cost order from highest to lowest to provide the first path.

39. A system for determining a path between a first endpoint and a second endpoint on a subnet comprising:

means for finding a first path from the first endpoint to a root bridge/switch of the subnet using a link layer data base;

means for finding a second path from a second endpoint to the root bridge/switch using the link layer data base;

means for removing non-utilized common nodes of the first path and the second path; and

means for connecting the first path and the second path at a common node.

40. The system of claim 39 wherein the link layer data base comprises link layer information obtained from at least one bridge/switch on the subnet that does not use layer three protocol information to process communications from a plurality of devices passing through the at least one bridge/subnet.

41. The system of claim 40 wherein the means for finding a first path further comprises:

means for identifying bridges/switches associated with the first endpoint in the link layer data base;

means for ordering the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.

42. A computer program product for finding a network segment path for a communication on a communication network supporting Internet protocol (IP) communications, the method comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which obtains link layer information from at least one connecting node on the communication network that does not use layer Internet three protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol; and

computer-readable program code which determines the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three Internet protocol information to process communications from a plurality of devices passing through the at least one connecting node based on the Internet protocol.

43. The computer program product of claim 42 wherein the at least one connecting node is a bridge/switch.

44. The computer program product of claim 43 wherein the computer-readable program code which obtains link layer information further comprises computer-readable program code which obtains an identification of the plurality of devices from the bridge/switch, the identification including a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices.

45. The computer program product of claim 44 further comprising computer-readable program code which stores obtained MAC addresses and associated connecting port numbers along with an identification of the bridge/switch and the respective ones of the plurality of devices as records in a link layer data base.

46. The computer program product of claim 45 wherein the computer-readable program code which stores further comprises computer-readable program code which time stamps the records and wherein computer-readable program code which obtains link layer information further comprises computer-readable program code which ages out records in the link layer data base.

47. A computer program product for finding a network segment path for a communication on a communication network, comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which obtains link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch, the computer-readable program code which obtains link layer information including computer-readable program code which obtains an identification of the plurality of devices from the bridge/switch, the identification including a media access controller (MAC) address and an associated connecting port number of the bridge/switch for the plurality of devices; and

computer-readable program code which determines the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

wherein the computer-readable program code which obtains an identification further comprises computer-readable program code which iteratively queries the bridge/switch for next entries in an address table of the bridge/switch using MIB commands until all entries in the address table have been obtained.

48. The computer program product of claim 47 wherein the computer-readable program code which iteratively queries the bridge/switch for next entries further comprises computer-readable program code which initiates communications traffic by the plurality of devices on the subnet if a specified time is exceeded before all entries in the address table have been obtained.

49. A computer program product for finding a network segment path for a communication on a communication network, comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which obtains link layer information from a bridge/switch on the communication network that does not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

computer-readable program code which determines the network segment path for the communication on the communication network based on the obtained link layer information, the network segment path including an identification of connecting nodes in the network segment path that do not use layer three protocol information to process communications from a plurality of devices passing through the bridge/switch; and

wherein the communication is between a first device and a second device and wherein the computer-readable program code which determines the network segment path for a communication over the communication network comprises;

computer-readable program code which determines a network path between the first device and the second device;

computer-readable program code which identifies subnets in the network path; and

computer-readable program code which determines a subnet path for each of the identified subnets in the network path using a link layer data base.

50. The method of claim 49 wherein the computer-readable program code which identifies subnets in the network path further comprises computer-readable program code which identifies a first endpoint and a second endpoint in the network path for each subnet in the network path and wherein the computer-readable program code which determines a subnet path further comprises:

computer-readable program code which finds a first path from the first endpoint to a root bridge/switch of a subnet using the link layer data base;

computer-readable program code which finds a second path from the second endpoint to the root bridge/switch of the subnet using the link layer data base;

computer-readable program code which removes non-utilized common nodes of the first path and the second path; and

computer-readable program code which connects the first path and the second path at a common node.

51. The computer program product of claim 50 wherein the computer-readable program code which finds a first path further comprises:

computer-readable program code which identifies bridges/switches associated with the first endpoint in the link layer data base;

computer-readable program code which orders the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.

52. The computer program product of claim 51 further comprising computer-readable program code which identifies in the link layer data base additional bridges/switches associated with the identified bridges/switches and wherein the computer-readable program code which orders the identified bridges/switches further comprises computer-readable program code which orders the identified bridges/switches associated with the first endpoint and the additional bridges/switches in root cost order from highest to lowest to provide the first path.

53. A computer program product for determining a path between a first endpoint and a second endpoint on a subnet comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which finds a first path from the first endpoint to a root bridge/switch of the subnet using a link layer data base;

computer-readable program code which finds a second path from a second endpoint to the root bridge/switch using the link layer data base;

computer-readable program code which removes non-utilized common nodes of the first path and the second path; and

computer-readable program code which connects the first path and the second path at a common node.

54. The computer program product of claim 53 wherein the link layer data base comprises link layer information obtained from at least one bridge/switch on the subnet that does not use layer three protocol information to process communications from a plurality of devices passing through the at least one bridge/subnet.

55. The computer program product of claim 54 wherein the computer-readable program code which finds a first path further comprises:

computer-readable program code which identifies bridges/switches associated with the first endpoint in the link layer data base;

computer-readable program code which orders the identified bridges/switches associated with the first endpoint in root cost order from highest to lowest to provide the first path.