Methods and devices for discovering the topology of large multi-subnet LANs

• US 20060256733A1
• Filed: 05/12/2005
• Published: 11/16/2006
• Est. Priority Date: 05/12/2005
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bejerano, Yigal
• Application Number:
  US11/127,082
• Publication Number:
  US 20060256733A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

The physical topology of large, heterogeneous Ethernet LANs that may include multiple subnets may be discovered utilizing Management Information Base (MIB) information. Topology discovery tools and network management systems are introduced to carry out the topological discovery methods, features and functions of the present invention.

Claims

1. A method for determining the topology of a multi-subnet, heterogeneous network comprising the steps of:

forming a preliminary topology based on address forwarding table (AFT) information obtained from one or more network elements (NEs) through SNMP queries; and

identifying one or more NEs that do not respond to SNMP queries and NEs adjacent to the identified NEs,

wherein the identified NEs are used to form a final topology.

2. The method as in claim 1 further comprising the steps of:

merging the identified NEs and associated edge connections from subnets that share an NE in common to form the final topology.

3. A method for determining the topology of a multi-subnet heterogeneous network comprising the steps of:

determining one or more connecting trees representing nodes in a subnet using address forwarding table (AFT) information;

forming skeleton-trees representing the connecting trees;

iteratively merging one or more pairs of skeleton trees, each tree associated with a common anchor node, to obtain a complete topology.

4. The method as in claim 3 wherein the AFT information is not complete AFT information for every node in the network.

5. The method as in claim 3 further comprising the step of obtaining the AFT information from backward learning operations on active ports.

6. The method as in claim 5 further comprising the steps of obtaining MAC addresses from each active port, wherein each MAC address represents the address of a source of packets.

7. The method as in claim 3 further comprising the steps of:

populating one or more AFTs using a common router; and

collecting AFT information using SNMP queries.

8. The method as in claim 3 further comprising the step of augmenting an AFT with an anchor node.

9. The method of claim 3 further comprising the step of compiling a list of ordered nodes according to their associated |B_v| values,

where B_v indicates a number of network elements in a subnet included in a sub-tree rooted by node ν

.

10. The method as in claim 9 further comprising the step of utilizing the list to determine a skeleton tree for each subnet.

11. The method as in claim 9 further comprising the step of utilizing the list to merge pairs of skeleton trees.

12. The method as in claim 3 wherein the network comprises a virtual local area network.

13. A device for determining the topology of a multi-subnet, heterogeneous network operable to:

form a preliminary topology based on address forwarding table (AFT) information obtained from one or more network elements (NEs) through SNMP queries; and

identify one or more NEs that do not respond to SNMP queries and NEs adjacent to the identified NEs,

wherein the identified NEs are used to form a final topology.

14. The device as in claim 13 further operable to:

merge the identified NEs and associated edge connections from subnets that share an NE in common to form the final topology.

15. A device for determining the topology of a multi-subnet heterogeneous network operable to:

determine one or more connecting trees representing nodes in a subnet using address forwarding table (AFT) information;

form skeleton-trees representing the connecting trees; and

iteratively merge one or more pairs of skeleton trees, each tree associated with a common anchor node, to obtain a complete topology.

16. The device as in claim 15 wherein the AFT information is not complete AFT information for every node in the network.

17. The device as in claim 15 further operable to obtain the AFT information from backward learning operations on active ports.

18. The device as in claim 17 further operable to obtain MAC addresses from each active port, wherein each MAC address represents the address of a source of packets.

19. The device as in claim 15 further operable to:

populate one or more AFTs using a common router; and

collect AFT information using SNMP queries.

20. The device as in claim 15 further operable to augment an AFT with an anchor node.

21. The device of claim 15 further operable to compile a list of ordered nodes according to their associated |B_v| values,

where B_v indicates a number of network elements in a subnet included in a sub-tree rooted by node ν

.

22. The device as in claim 21 further operable to utilize the list to determine a skeleton tree for each subnet.

23. The device as in claim 21 further operable to utilize the list to merge pairs of skeleton trees.

24. The device as in claim 23 wherein the device comprises a controller used in a network management system.

25. The device as in claim 23 wherein the device comprises a topology discovery tool.

26. The device as in claim 15 wherein the network comprises a virtual local area network.