Ethernet Topology Discovery: A Survey
---
paper_title: A scalable content-addressable network

paper_content:

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.
---
paper_title: Topology discovery in heterogeneous IP networks: the NetInventory system

paper_content:

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.
---
paper_title: Discovering Network Topology of Large Multisubnet Ethernet Networks

paper_content:

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.
---
paper_title: Chord: a scalable peer-to-peer lookup protocol for internet applications

paper_content:

A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis and simulations show that Chord is scalable: Communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
---
paper_title: Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design

paper_content:

Despite recent excitement generated by the peer-to-peer (P2P) paradigm and the surprisingly rapid deployment of some P2P applications, there are few quantitative evaluations of P2P systems behavior. The open architecture, achieved scale, and self-organizing structure of the Gnutella network make it an interesting P2P architecture to study. Like most other P2P applications, Gnutella builds, at the application level, a virtual network with its own routing mechanisms. The topology of this virtual network and the routing mechanisms used have a significant influence on application properties such as performance, reliability, and scalability. We have built a "crawler" to extract the topology of Gnutella's application level network. In this paper we analyze the topology graph and evaluate generated network traffic. Our two major findings are that: (1) although Gnutella is not a pure power-law network, its current configuration has the benefits and drawbacks of a power-law structure, and (2) the Gnutella virtual network topology does not match well the underlying Internet topology, hence leading to ineffective use of the physical networking infrastructure. These findings guide us to propose changes to the Gnutella protocol and implementations that may bring significant performance and scalability improvements. We believe that our findings as well as our measurement and analysis techniques have broad applicability to P2P systems and provide unique insights into P2P system design tradeoffs.
---
paper_title: Characterizing unstructured overlay topologies in modern P2P file-sharing systems

paper_content:

In recent years, peer-to-peer (P2P) file-sharing systems have evolved to accommodate growing numbers of participating peers. In particular, new features have changed the properties of the unstructured overlay topologies formed by these peers. Little is known about the characteristics of these topologies and their dynamics in modern file-sharing applications, despite their importance. This paper presents a detailed characterization of P2P overlay topologies and their dynamics, focusing on the modern Gnutella network. We present Cruiser, a fast and accurate P2P crawler, which can capture a complete snapshot of the Gnutella network of more than one million peers in just a few minutes, and show how inaccuracy in snapshots can lead to erroneous conclusions-such as a power-law degree distribution. Leveraging recent overlay snapshots captured with Cruiser, we characterize the graph-related properties of individual overlay snapshots and overlay dynamics across slices of back-to-back snapshots. Our results reveal that while the Gnutella network has dramatically grown and changed in many ways, it still exhibits the clustering and short path lengths of a small world network. Furthermore, its overlay topology is highly resilient to random peer departure and even systematic attacks. More interestingly, overlay dynamics lead to an ldquoonion-likerdquo biased connectivity among peers where each peer is more likely connected to peers with higher uptime. Therefore, long-lived peers form a stable core that ensures reachability among peers despite overlay dynamics.
---
paper_title: Ethernet topology discovery without network assistance

paper_content:

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.
---
paper_title: Topology discovery for large ethernet networks

paper_content:

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.
---
paper_title: Capturing accurate snapshots of the Gnutella network

paper_content:

A common approach for measurement-based characterization of peer-to-peer (P2P) systems is to capture overlay snapshots using a crawler. The accuracy of captured snapshots by P2P crawlers directly depends on both the crawling speed and the fraction of unreachable peers. This in turn affects the accuracy of the conducted characterization based on these captured snapshots. Prior studies frequently rely on crawling the network over an hour or more, during which time the overlay may change substantially. Moreover, none of the previous measurement-based studies on P2P systems have examined the accuracy of their captured snapshots or the impact on conducted characterization.
---
paper_title: Topology discovery in heterogeneous IP networks

paper_content:

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.
---
paper_title: Measuring ISP topologies with rocketfuel

paper_content:

To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to directly measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, exploiting properties of IP routing to eliminate redundant measurements, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the inter-domain peering structure. As part of this work, we release our maps to the community.
---
paper_title: Ethernet Topology Discovery for Networks with Incomplete Information

paper_content:

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.
---
paper_title: Heuristics for Internet map discovery

paper_content:

Mercator is a program that uses hop-limited probes-the same primitive used in traceroute-to infer an Internet map. It uses informed random address probing to carefully exploring the IP address space when determining router adjacencies, uses source-route capable routers wherever possible to enhance the fidelity of the resulting map, and employs novel mechanisms for resolving aliases (interfaces belonging to the same router). This paper describes the design of these heuristics and our experiences with Mercator, and presents some preliminary analysis of the resulting Internet map.
---
paper_title: In search of path diversity in ISP networks

paper_content:

Internet Service Providers (ISPs) can exploit path diversity to balance load and improve robustness. Unfortunately, it is difficult to evaluate the potential impact of these approaches without routing and topological data, which are confidential. In this paper, we characterize path diversity in the real Sprint network. We then characterize path diversity in ISP topologies inferred using the Rocketfuel tool. Comparing the real Sprint topology to the one inferred by Rocketfuel, we find that the Rocketfuel topology has significantly higher apparent path diversity.(As a metric, path diversity is particularly sensitive to the presence of false or missing links, both of which are artifacts of active measurement techniques.) We evaluate heuristics that improve the accuracy of the inferred Rocketfuel topologies. Finally, we discuss limitations of active measurements techniques to capture topological properties such as path diversity.
---
paper_title: Characterization of Layer-2 Unique Topologies in Multisubnet Local Area Networks

paper_content:

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
---
paper_title: Characterization of layer-2 unique topologies

paper_content:

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.
---
paper_title: Mapping the Internet

paper_content:

How can you determine what the Internet or even an intranet looks like? The answer is, of course, to draw it on screen. Once you can see the data succinctly, it becomes much easier to understand. The drawing itself can help locate bottlenecks and possible points of failure. Where is that newly acquired subsidiary connected? Which business units have connections to business partners? More important, visual displays of networks have another dimension-color. Color is an easy way to display link use, status, ownership, and network changes.
---
paper_title: Checkmate network security modeling

paper_content:

Effective reasoning about system attacks and responses requires a comprehensive model that covers all aspects of the system being analyzed, from network topology and configuration, to specific vulnerabilities, to possible adversary capabilities and possible attacks. A comprehensive model can be used as the basis for real-time attack/response simulations "what if" course of action analysis, policy simulation and debugging, and more. This paper describes the Checkmate security model and illustrates how this model can be used as the basis for a tool that performs effective security analysis on real-world networks.
---
paper_title: Topology discovery in heterogeneous IP networks: the NetInventory system

paper_content:

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.
---
paper_title: On realistic network topologies for simulation

paper_content:

Simulations are an important tool in network research. As the selected topology often influences the outcome of the simulation, realistic topologies are needed to produce realistic simulation results. We first discuss the different types of topologies and present our collection of real-world topologies that can be used for simulation. We then define several similarity metrics to compare artificially generated topologies with real world topologies. We use them to find out what the input parameter range of the topology generators of BRITE, TIERS and GTITM are to create realistic topologies. These parameters can act as a valuable starting point for researchers that have to generate artificial topologies.
---
paper_title: Composable tools for network discovery and security analysis

paper_content:

Security analysis should take advantage of a reliable knowledge base that contains semantically-rich information about a protected network. This knowledge is provided by network mapping tools. These tools rely on models to represent the entities of interest, and they leverage off network discovery techniques to populate the model structure with the data that is pertinent to a specific target network. Unfortunately, existing tools rely on incomplete data models. Networks are complex systems and most approaches oversimplify their target models in an effort to limit the problem space. In addition, the techniques used to populate the models are limited in scope and are difficult to extend. This paper presents NetMap, a security tool for network modeling, discovery, and analysis. NetMap relies on a comprehensive network model that is not limited to a specific network level; it integrates network information throughout the layers. The model contains information about topology, infrastructure, and deployed services. In addition, the relationships among different entities in different layers of the model are made explicit. The modeled information is managed by using a suite of composable network tools that can determine various aspects of network configurations through scanning techniques and heuristics. Tools in the suite are responsible for a single, well-defined task.
---
paper_title: Ethernet topology discovery without network assistance

paper_content:

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.
---
paper_title: Topology discovery for large ethernet networks

paper_content:

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.
---
paper_title: Topology Discovery for Public IPv6 Networks

paper_content:

This paper presents Atlas,a system that facilitates the automated capture of IPv6 network topology information from a single probing host.It describes the Atlas infrastructure and its data collection processes.We also present some initial results from our probing of the 6Bone,currently the largest public IPv6 network.The results illustrate the effectiveness of the probing algorithm and also identify some trends in prefix allocation and routing policy.
---
paper_title: Topology discovery in heterogeneous IP networks

paper_content:

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.
---
paper_title: Distributed agent-based real time network intrusion forensics system architecture design

paper_content:

Network forensics is a new approach for the network security, because the firewall and IDS cannot always stop and discover the misuse in the network. Once the system is compromised, the forensics and investigation always after the attacks and lose some useful instant evidence. The integrated analysis of the log and audit system and network traffic can lead to an efficient navigation of the traffic. The current network forensics approaches only focus on the network traffic capture and traffic replay, which always result in the performance bottleneck or forensics analysis difficulties. However, the adaptive capture without lose the potential sensitive traffic and real time investigation are seldom discussed. In this paper, we discuss the frameworks of distributed agent-based real time network intrusion forensics system, which is deployed in local area network environment. Some novel approaches for network forensics are discussed for the first time, such as network forensics server, network forensics database, network forensics agents, forensics data integration and active real time network forensic.
---
paper_title: Network forensics analysis

paper_content:

Many tools let you view traffic in real time, but real-time monitoring at any level requires significant human and hardware resources, and doesn't scale to networks larger than a single workgroup. It is generally more practical to archive all traffic and analyze subsets as necessary. This process is known as reconstructive traffic analysis, or network forensics. In practice, it is often limited to data collection and packet-level inspection; however, a network forensics analysis tool can provide a richer view of the data collected, allowing you to inspect the traffic from further up the protocol stack? The IT industry's ever-growing concern with security is the primary motivation for network forensics. A network that has been prepared for forensic analysis is easy to monitor, and security vulnerabilities and configuration problems can be conveniently identified. It also allows the best possible analysis of security violations. Most importantly, analyzing a complete record of your network traffic with the appropriate reconstructive tools provides context for other breach-related events.
---
paper_title: Ethernet topology discovery without network assistance

paper_content:

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.
---
paper_title: A scalable content-addressable network

paper_content:

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.
---
paper_title: Characterizing unstructured overlay topologies in modern P2P file-sharing systems

paper_content:

In recent years, peer-to-peer (P2P) file-sharing systems have evolved to accommodate growing numbers of participating peers. In particular, new features have changed the properties of the unstructured overlay topologies formed by these peers. Little is known about the characteristics of these topologies and their dynamics in modern file-sharing applications, despite their importance. This paper presents a detailed characterization of P2P overlay topologies and their dynamics, focusing on the modern Gnutella network. We present Cruiser, a fast and accurate P2P crawler, which can capture a complete snapshot of the Gnutella network of more than one million peers in just a few minutes, and show how inaccuracy in snapshots can lead to erroneous conclusions-such as a power-law degree distribution. Leveraging recent overlay snapshots captured with Cruiser, we characterize the graph-related properties of individual overlay snapshots and overlay dynamics across slices of back-to-back snapshots. Our results reveal that while the Gnutella network has dramatically grown and changed in many ways, it still exhibits the clustering and short path lengths of a small world network. Furthermore, its overlay topology is highly resilient to random peer departure and even systematic attacks. More interestingly, overlay dynamics lead to an ldquoonion-likerdquo biased connectivity among peers where each peer is more likely connected to peers with higher uptime. Therefore, long-lived peers form a stable core that ensures reachability among peers despite overlay dynamics.
---
paper_title: Capturing accurate snapshots of the Gnutella network

paper_content:

A common approach for measurement-based characterization of peer-to-peer (P2P) systems is to capture overlay snapshots using a crawler. The accuracy of captured snapshots by P2P crawlers directly depends on both the crawling speed and the fraction of unreachable peers. This in turn affects the accuracy of the conducted characterization based on these captured snapshots. Prior studies frequently rely on crawling the network over an hour or more, during which time the overlay may change substantially. Moreover, none of the previous measurement-based studies on P2P systems have examined the accuracy of their captured snapshots or the impact on conducted characterization.
---
paper_title: Mapping the Internet

paper_content:

How can you determine what the Internet or even an intranet looks like? The answer is, of course, to draw it on screen. Once you can see the data succinctly, it becomes much easier to understand. The drawing itself can help locate bottlenecks and possible points of failure. Where is that newly acquired subsidiary connected? Which business units have connections to business partners? More important, visual displays of networks have another dimension-color. Color is an easy way to display link use, status, ownership, and network changes.
---
paper_title: Topology discovery in heterogeneous IP networks: the NetInventory system

paper_content:

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.
---
paper_title: Discovering Network Topology of Large Multisubnet Ethernet Networks

paper_content:

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.
---
paper_title: Ethernet topology discovery without network assistance

paper_content:

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.
---
paper_title: Topology discovery for large ethernet networks

paper_content:

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.
---
paper_title: Topology discovery in heterogeneous IP networks

paper_content:

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.
---
paper_title: Ethernet Topology Discovery for Networks with Incomplete Information

paper_content:

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.
---
paper_title: Characterization of Layer-2 Unique Topologies in Multisubnet Local Area Networks

paper_content:

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
---
paper_title: Characterization of layer-2 unique topologies

paper_content:

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.
---

Title: Ethernet Topology Discovery: A Survey

Section 1: INTRODUCTION
Description 1: Provide an overview of the focus of the survey, the importance of Ethernet network topology discovery, and a summary of different types of network topologies.

Section 2: MOTIVATIONS
Description 2: Discuss the various applications and benefits of Ethernet network topology information in network administration, performance prediction, protocol design, simulation, and security.

Section 3: NETWORK NODE DISCOVERY
Description 3: Explain the process of identifying unique network nodes in Ethernet networks, differentiating between active and passive nodes, and the importance of discovering dumb network devices.

Section 4: NETWORK TOPOLOGY INFERENCE
Description 4: Describe the methods and algorithms used to infer network topologies, the challenges associated with different network environments, and details of the SNMP and non-SNMP based topology discovery techniques.

Section 5: LIMITATIONS AND ISSUES
Description 5: Outline the limitations and issues related to current Ethernet topology discovery methods, including network topology changes, VLANs, and integration of wireless and mobile nodes.

Section 6: CONCLUSION
Description 6: Summarize the significance of network topology discovery, the advancements made in this field, and the ongoing challenges and potential future directions for research.