Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either: (a) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored; or (b) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of a topology discovery tool that has been tested on Lucent's own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology in time that is roughly quadratic in the number of network elements. <s> BIB001 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> Accurate network topology information is important for both network management and application performance prediction. Most topology discovery research has focused on wide-area networks and examined topology only at the IP router level, ignoring the need for LAN topology information. Recent work has demonstrated that bridged Ethernet topology can be determined using standard SNMP MIBs; however, these algorithms require each bridge to learn about all other bridges in the network. Our approach to Ethernet topology discovery can determine the connection between a pair of the bridges that share forwarding entries for only three hosts. This minimal knowledge requirement significantly expands the size of the network that can be discovered. We have implemented the new algorithm, and it has accurately determined the topology of several different networks using a variety of hardware and network configurations. Our implementation requires access to only one endpoint to perform the queries needed for topology discovery. <s> BIB002 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either 1) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored, or 2) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of the NetInventory topology-discovery tool that has been tested on Lucent's own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology with reasonably small running-time requirements even for fairly large network configurations. <s> BIB003 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> This work addresses the problem of layer 2 topology discovery. Current techniques concentrate on using SNMP to query information from Ethernet switches. In contrast, we present a technique that infers the Ethernet (layer 2) topology without assistance from the network elements by injecting suitable probe packets from the end-systems and observing where they are delivered. We describe the algorithm, formally characterize its correctness and completeness, and present our implementation and experimental results. Performance results show that although originally aimed at the home and small office the techniques scale to much larger networks. <s> BIB004 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> 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 <s> BIB005 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> 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. <s> BIB006 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> 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. <s> BIB007 </s> Ethernet Topology Discovery: A Survey <s> IV. NETWORK TOPOLOGY INFERENCE <s> In this paper we study a layer-2 topology restoration for multisubnet networks. We design a new algorithm for generating such topologies and prove a criterion on a set of input data that guarantees a unique layer-2 topology. Our criterion is easily verifiable in O(n^2) time, where n is the number of internal network nodes. <s> BIB008
A network's physical topology can potentially correspond to several logical topologies depending on the level of abstraction used. In 2000 Breitbart et al BIB001 realized that network management tools as well as previous research efforts focused on layer 3 topology discovery and ignored the connectivity of layer 2 network elements. Where layer 2 topology discovery tools did exist, they were found to specifically target single vendor products BIB001 . Breitbart et al therefore developed algorithms that could perform layer 2 topology discovery in multi-vendor (heterogeneous) networks (See Figure 2) Breitbart et al also observed that for multisubnet networks the network topology may not be unique even for the set of complete AFTs obtained from a simple Ethernet network. Breitbart et al proposed a newer algorithm that could successfully discover the target network topology, provided that the network was uniquely described by the SNMP MIB data obtained BIB003 . In such a case finding an exact topology is not possible. However, their algorithm from generates some network fragments that can be uniquely determined. Lowekamp et al. relaxed the dependency on complete AFTs information BIB002 and proposed a necessary and sufficient condition for two AFTs to be connected (directly or indirectly). Their work also addressed the topologies that may contain uncooperative nodes, which are the nodes that can appear in other nodes' AFTs but don't provide access to their own AFTs. The work described in BIB002 could discover the topology with only limited AFT data collected from SNMP enabled network elements. However, their approach may fail to discover the topology even in simple networks as observed by Gobjuka and Breitbart BIB006  . Bejerano et al.  proposed the first formal algorithm to discover the topology in presence of uncooperative elements (i.e. hubs.) Uncooperative elements do not speak SNMP, do not allow access or do not even have layer 2 addresses. The main issue with this algorithm was its complexity; the algorithm was too complex to understand and implement in practice. Furthermore, this method may not discover any topology if the given input set of AFTs defines a non-unique topology. Sun et al   proposed an algorithm based on "connections reasoning technique" that was claimed to be necessary and sufficient to discover the layer 2 topology even when the information provided by nodes MIBs is incomplete. However, their claim was not supported by proofs. Furthermore, the incorrectness of these claims was shown by Gobjuka and Breitbart BIB006  by proving that discovering Ethernet topology when AFTs are incomplete is, in fact, an NP-hard problem, even if the network comprises a single subnet. Further work by Bejerano  showed the limitations of the algorithms developed by Lowekamp et al BIB002 and Breitbart et al BIB001 BIB003 in multi-subnet networks or in the presence of uncooperative switches and hubs. Bejerano's algorithm was simple and could discover the topology in most of cases. However, it cannot guarantee a topology discovery. Also, his method also requires a completeness of input AFTs. Research by Stott [41] also employed SNMP MIB data, but instead of using forwarding table data, the algorithm used data from the Bridge-MIB. However, the method described in this paper assumes that each device has knowledge of the spanning tree root, which doesn't happen always in practice. Gobjuka and Breitbart BIB008 BIB005 described the first formal method to determine whether a given set of complete AFTs define a unique topology when the network doesn't contain hubs. They also showed that there is proportional relationship between the number of subnets in the network and non-uniqueness of the discovered topology. Further work by Gobjuka and Breitbart BIB007 described the first practical algorithm to discover the Ethernet network topology when the network contains hubs. Their methods discover the all network topologies when the MIB information defines more than one topology. Furthermore, they proposed criteria to decide the uniqueness of network topology from a complete set of AFTs when the network contains hubs. More recently, Gobjuka and Breitbart BIB006  investigated the problem of finding the layer 2 topology for networks that may include uncooperative nodes when the available AFTs are incomplete. They proved that finding a layer 2 network topology for a given set of incomplete AFTs is an NP-hard problem even for single subnet networks and deciding whether a given set of AFTs defines a unique network topology is a co-NP-hard problem. The authors showed that the topology discovery problem is NP-hard even if there are two nodes "a" and "b" in the network such that node "a" appears in some AFTs and node "b" appears in some AFTs but neither "a" nor "b" appears in all AFTs. This condition was probably the strongest which makes the problem NP-hard as they also showed that the topology can be discovered in polynomial time if all AFTs include node "a". They also proposed heuristic algorithms to find network topology BIB006  . Their also described methods for inferring complete AFTs from incomplete information. This approach is used in heuristic that discovers the topology from incomplete AFTs. The Internet Engineering Task Force (IETF) attempted to create a standard for SNMP topology discovery by creating the Physical Topology MIB, but adoption of the proposal was hampered by the fact that it did not include details on how to actually populate the required MIB objects. To remedy the situation, the IEEE developed the Link Layer Discovery Protocol (LLDP) as part of the 802.1AB-2005 standard. The LLDP allows neighboring devices to become aware of each other and populate their Physical Topology MIBs. The efforts surrounding LLDP clearly shows an industry need for topology discovery in heterogeneous networks at layer 2; however, LLDP cannot easily be deployed on legacy equipment. All the layer 2 topology discovery techniques and algorithms discussed thus far depend on SNMP enabled network elements. The reliance on SNMP can prove problematic in quite a number of network environments. As networks grow and management becomes decentralized it cannot be assumed that SNMP would be enabled or that administrative SNMP access would be granted. A lot of small business, home office and branch office networks are built using consumer-grade network equipment that do not even support SNMP. A need for topology discovery techniques that do not require network cooperation and for tools that can augment SNMP-based techniques therefore exists. A technique for layer 2 topology discovery without network element cooperation has been implemented by Black et al BIB004 . The technique exploits the packet forwarding properties of network elements, specifically those of switches. The algorithm requires specialized software on many edge nodes (hosts) that are controlled from a master node to execute the distributed discovery algorithm BIB004 . Cooperating hosts train switches they are connected to in order to only pass packets with specific addresses. The master node then instructs other hosts to send probe packets with the specific addresses. Depending on where the probe packets are delivered to (or not), a picture of the network internals can be formed. The problem with this method is that special software agents have to be installed on network hosts. Other efforts worth mentioning are proprietary protocols by network vendors used prior to the standardization of the LLDP. These include the Cisco Discovery Protocol (CDP), Enterasys Networks' Cabletron Discovery Protocol (also CDP), Extreme Networks' Extreme Discovery Protocol (EDP) and Nortel Networks' Nortel Discovery Protocol (NDP). The use of Ethernet as an access technology, especially in the telecommunication industry, has also led to efforts to add and standardize Ethernet capabilities for Operational, Administration and Maintenance (OAM) management. The main operational issues addressed are discovery, link monitoring, and fault signaling and remote loopback. The added functionality is not aimed specifically at topology discovery in enterprise networks, but could potentially be used.