Taking The Skeletons Out Of the Closets: A Simple And Efficient Topology Discovery Scheme for Large Multi-subnet LANs

Modern enterprises LANs are, typically, large networks comprising multiple-vendor equipment. Their complexity raises considerable challenges to perform critical management tasks, such as network diagnostic, and it is practically impossible without an up- to-date knowledge of the physical network topology. Given the dynamic nature of today's LANs, keeping track of topology information manually is a daunting (if not impossible) task. Consequently, effective schemes for automatic inference of physical network topology are essential. In this paper, we propose a simple and efficient algorithmic solution for discovering the physical topology of a large, heterogeneous Ethernet LANs that may include multiple subnets as well as uncooperative network elements, such as hubs. Our scheme utilizes only generic MIB information and does not require any hardware or software modification of the explored network elements. By rigorous analysis, we prove that our solution provides the correct network topology and its communication as well as computational complexity is very low. Our extensive simulations show that the scheme succeeds to infer the complete topology in the vast majority of the cases, including many instances that other methods fail. Finally, to verify the scheme practicality, we implemented a topology discovery tool and used it to discover the topology of our organization network. These properties support the practicality of our scheme for network management.