Physical Topology Discovery for Large Multi-Subnet Networks
01 January 2003
In this paper we propose the first complete algorithmic solution for discovering the physical topology of a large, heterogeneous Ethernet network comprising multiple subnets as (possibly) dumb or uncooperative network elements. Our algorithms rely on standard SNMP MIB information that is widely supported in modern IP networks and require no modifications to the operating system software running on elements or hosts. Furthermore, we formally demonstrate that our solution is complete for the given MIB data; that is, if the MIB information is suffifcient to uniquely identify the network topology then our algorithm is guaranteed to recover it. To the best of our knowledge, ours is the first solution to provide such a strong completeness guarantee.