Method and system for network topology discovery

1. A network appliance for topology discovery of a network comprising a plurality of heterogeneous devices, each device having at least one port, the network appliance comprising:

a processor; and

a computer readable medium storing processor-executable instructions organized into:

a data acquisition and validation module for data collection from said plurality of heterogeneous devices and validating received data to ensure correctness and completeness;

a device identification and classification module for:

identifying active devices among said plurality of heterogeneous devices and producing a set of identified devices; and

classifying each said identified device according to values of device descriptors acquired from said set of identified devices, said device descriptors being selected from a specified set of device descriptors;

and

a topology deduction module for synthesizing a network-topology image according to:

classifications of said set of identified devices;

address-forwarding data acquired from each port of each device among said set of identified devices; and

a set of encoded connectivity patterns, each connectivity pattern defined by devices of specific device types and respective media-access data.

2. The network appliance of claim 1 , further comprising a network interface module having stored thereon processor-readable instructions to cause said processor to:

communicate with said plurality of heterogeneous devices through a shared network;

format data sent to said heterogeneous devices; and

interpret data received from said heterogeneous devices.

3. The network appliance of claim 1 , further comprising one of:

a direct connection to a selected device from among said plurality of heterogeneous devices; and

remote access to said heterogeneous devices.

4. The network appliance of claim 1 , further comprising processor-readable instructions within said device identification and classification module to cause said processor to:

communicate with devices having IP addresses within a specified IP address range to identify responsive devices;

form a set of IP addresses of responsive devices; and

communicate with each responsive device to obtain values of said device descriptors.

5. The network appliance of claim 1 , further comprising processor-readable instructions within said topology deduction module to cause said processor to:

sort said encoded connectivity patterns according to topological dependency;

initialize said network-topology image to comprise unconnected devices of said set of identified devices;

identify all occurrences of said each connectivity pattern; and

incorporate said all occurrences in said network-topology image.

6. The network appliance of claim 1 , further comprising processor-readable instructions within said topology deduction module to cause said processor to:

select a target switch among said plurality of heterogeneous devices;

select a port in said target switch;

acquire an address forwarding table for said port;

where said address forwarding table includes multiple entries, all corresponding to end devices among said set of identified devices, insert an unmanaged node connecting said end devices to said port in said network-topology image.

7. The network appliance of claim 1 , further comprising processor-readable instructions within said topology deduction module to cause said processor to:

identify a first switch among said plurality of heterogeneous devices;

identify a second switch among said plurality of heterogeneous devices;

select a port pair, a first port from among ports of said first switch and a second port from among ports of said second switch;

acquire a first address-forwarding table of said first port and a second address-forwarding table of said second port;

where said first address forwarding table and said second address forwarding table are non-intersecting and have a complete union, a complete union occupying an entire address space, ascertain direct connectivity between said first switch and said second switch;

where said first address forwarding table and said second address forwarding table have a complete union and common end devices, insert an unmanaged node connecting said end devices to said port pair in said network-topology image.

8. The network appliance of claim 1 wherein said device descriptors determine presence of at least one of:

a simple-network-management-protocol agent;

IP-switching capability;

characterization of a device as one of:

an end device with an SNMP agent;

a layer-2 switch;

a router; and

a layer-3 switch;

management information base; and

forwarding media-access-control addresses.

9. The network appliance of claim 1 wherein:

at least one descriptor is a root descriptor having has at least one successor descriptor and no preceding descriptors; and

a value of a descriptor indicates one of:

a device type from among a set of predefined device types; and

a successor descriptor.

10. The network appliance of claim 1 wherein said connectivity patterns are arranged into multiple strata, wherein connectivity patterns of each stratum are independent from each other and from connectivity patterns of any succeeding stratum.

11. The network appliance of claim 1 wherein said set of connectivity patterns comprise:

end devices directly connected to a switch;

directly connected switches;

an unmanaged node connecting switches and having subtending end devices;

unmanaged nodes connecting edge devices;

an unmanaged node connecting multiple switches; and

unmanaged nodes with each unmanaged node connecting more than two switches.

12. A method of topology discovery of a network comprising a plurality of heterogeneous devices, the method, implemented by a network appliance having a processor, comprising:

collecting data from said plurality of heterogeneous devices;

validating received data to ensure correctness and completeness;

identifying active devices among said plurality of heterogeneous devices to produce a set of identified devices; and

classifying each said identified device according to values of device descriptors acquired from said set of identified devices to produce classifications of said set of identified devices, said device descriptors being selected from a specified set of device descriptors; and

synthesizing a network-topology image according to:

classifications of said set of identified devices;

address-forwarding data acquired from each device among said set of identified devices; and

a set of encoded connectivity patterns, each connectivity pattern defined by devices of specific device types and respective media-access data.

13. The method of claim 12 further comprising:

communicating with said plurality of heterogeneous devices through a shared network;

formatting data sent to said heterogeneous devices; and

interpreting data received from said heterogeneous devices.

14. The method of claim 12 further comprising directly connecting said network appliance to a selected device from among said plurality of heterogeneous devices.

15. The method of claim 12 further comprising:

communicating with devices having IP addresses within a specified IP address range to identify responsive devices;

forming a set of IP addresses of responsive devices; and

communicating with each responsive device to obtain values of said device descriptors.

16. The method of claim 12 further comprising:

sorting said encoded connectivity patterns according to topological dependency;

initializing said network-topology image to comprise unconnected devices of said set of identified devices;

identifying all occurrences of said each connectivity pattern; and

incorporating said all occurrences in said network-topology image.

17. The method of claim 12 further comprising:

selecting a target device among said plurality of heterogeneous devices;

selecting a port in said target device;

acquiring an address forwarding table for said port;

where said address forwarding table includes multiple entries, all corresponding to end devices among said set of identified devices, inserting in said network-topology image an unmanaged node connecting said end devices to said port.

18. The method of claim 12 further comprising:

identifying a first switch among said plurality of heterogeneous devices;

identifying a second switch among said plurality of heterogeneous devices;

selecting a port pair, a first port from among ports of said first switch and a second port from among ports of said second switch;

acquiring a first address-forwarding table of said first port and a second address-forwarding table of said second port;

ascertaining direct connectivity between said first switch and said second switch subject to a determination that said first address forwarding table and said second address forwarding table are non-intersecting and have a complete union, where a complete union occupies an entire address space; and

inserting in said network-topology image an unmanaged node connecting said end devices to said port pair subject to a determination that said first address forwarding table and said second address forwarding table have a complete union and common end devices.

19. The method of claim 12 further comprising interpreting said device descriptors as an indication of presence of at least one of:

a simple-network-management-protocol agent;

IP-switching capability;

characterization of a device as one of:

an end device with an SNMP agent;

a layer-2 switch;

a router; and

a layer-3 switch;

management information base; and

forwarding media-access-control addresses.

20. The network appliance of claim 12 further comprising arranging said connectivity patterns into multiple strata, wherein connectivity patterns of each stratum are independent from each other and from connectivity patterns of any succeeding stratum.