In this paper we investigate the problem of finding the physical layer topology of large, heterogeneous networks that comprises multiple VLANs and may include uncooperative network nodes. We prove that finding a layer-2 network topology for a given incomplete input is an NP-hard problem even when the network comprises only two VLANs and the network contains one loop and deciding whether a given input defines a unique VLANs topology is a co-NP-hard problem. We design several heuristic algorithms to find VLANs topology. Our first algorithm is designed for geographically wide-spread networks that may contain uncooperative devices. For such networks the algorithm discovers the topology for each VLAN then merges them to infer the network topology in 0(n3) time, where n is the number of internal network nodes. Our second algorithm is designed for smaller, active networks where each device in the network provides access to their MIB and few AFT entries are missing. For such networks, the algorithm finds the unique topology of VLANs in O(n3) time. We have implemented both the algorithms described in this paper and conducted extensive experiments on multiple networks. Our experiments demonstrate that our approach is quite practical and discovers the accurate VLANs topology of large and heterogeneous networks whose input may not necessarily be complete. To the best of our knowledge, this is the first paper investigating topology discovery for VLANs.

In this paper, we investigate the problem of finding the layer-2 network topology of large, heterogeneous multisubnet Ethernet networks that may include uncooperative network nodes. We prove that finding a layer-2 network topology for a given incomplete input is an NP-hard problem, even for single subnet networks, and that deciding whether a given input defines a unique network topology is a co-NP-hard problem. We design several heuristic algorithms to find network topology, evaluate their complexity, and provide criteria for instances in which the input guarantees a unique network topology. We have implemented one of our algorithms and conducted extensive experiments on the Kent State University Computer Science network. Our experiments demonstrate that our approach is quite practical and discovers the accurate network topology of multisubnet networks whose input may not necessarily be complete.

In this paper we investigate the problem of finding a layer-2 network topology when the information available from SNMP MIB is incomplete. We prove that finding a network topology in this case is NP-hard. We further prove that deciding whether the given information defines a unique network topology is a co-NP-hard problem. We show that if there is a single node r such that every other network node sees it, then the network topology can be discovered in polynomial (in the number of network ports) time. Finally, we design a polynomial time heuristic algorithm to discover a topology when the information available from SNMP MIB is incomplete and conduct extensive experiments with it to determine how often the algorithm succeeds in finding topology. Our results indicate that our algorithm discovers the network topology in close to 100% of all test cases.

In this paper we investigate the problem of finding the physical layer network topology of large, heterogeneous multisubnet Ethernet networks that may include uncooperative network elements. Our approach utilizes only generic MIB information and does not require any hardware or software modifications of the underlying network elements. We propose here the first O(n3) algorithm that guarantees discovering a topology that is compatible with the given set of input MIBs, provided that the input is complete. We prove the correctness of the algorithms and the necessary and sufficient conditions for the uniqueness of the restored topology. Finally, we demonstrate the application of the algorithm on several examples.

Obtaining network connectivity information (or, alternatively, network topology) at layer-2 of the ISO hierarchy is critical to an effective management of large local area networks (LANs) that include hundreds of layer-2 network elements. Despite the importance of getting a layer-2 network topology, there are several major difficulties in tracking this information

Various network monitoring and performance evaluation schemes generate considerable amount of traffic, which affects network performance. In this paper we describe a method for minimizing network monitoring overhead based on shortest path tree (SPT) protocol. We describe two different variations of the problem: the A-problem and the E-problem, and show that there is a significant difference between them. We prove that finding optimal solutions is NP-hard for both variations, and propose a theoretically best possible heuristic for the A-problem and three different heuristics for the E-problem, one of them being also theoretically best possible. We show that one can compute in polynomial time an O(ln|V|)-approximate solution for each of these problems. Then, we analyze the performance of our heuristics on large graphs generated using Waxman and power-law models as well as on real ISP topology maps. Experiment results show more than 80% improvement when using our heuristics on real topologies over the naive approaches