Taking the Skeletons Out of the Closets: A Simple and Efficient Topology Discovery Scheme for Large Ethernet LANs

We propose a simple and efficient algorithmic solution for discovering the physical topology of large, heterogeneous Ethernet LANs that may include multiple subnets as well as uncooperative network elements, like hubs. Our scheme utilizes only generic MIB information and does not require any hardware or software modification of the underlying network elements. By rigorous analysis, we prove that our method correctly infers the network topology and has low communication and computational overheads. Our simulation results show that the scheme successfully infers the complete topology in the vast majority of the cases, including many instances that cannot be inferred by other methods. Finally, our proof-of-concept implementation demonstrates the practicality of the proposed scheme for network management.