Taking The Skeletons Out Of The Closets: A Simple And Efficient Topology Discovery Scheme For Large Ethernet LANs

Today, Ethernet is the dominant local area network (LAN) technology. These networks, typically, comprise large numbers of elements from different vendors. This raises considerable difficulties in performing network management tasks, such as resource management and root cause analysis, which are 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. Therefore, it is essential to develop practical schemes for automatic inference of the physical topology of Ethernet networks. In this paper, 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 in which other methods fail. Finally, we implemented the proposed scheme to verify its inference capabilities. These properties confirm the practicality of our scheme for network management.