Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB001 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB002 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB003 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB004 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB005 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB006 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB007 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB008 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB009 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB010 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB011 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB012 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB013 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB014 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <s> 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. <s> BIB015 </s> Ethernet Topology Discovery: A Survey <s> I. INTRODUCTION <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> BIB016
This survey focuses on measurements of the Ethernet network topology, i.e., the representation of the interconnection between directly connected peers in the Ethernet network. While information about network devices (i.e nodes) and connections can be obtained by processing the data collected from the network and passive measurements, researchers largely obtain information about network nodes, topology and its characteristics from active measurements. There are three different levels at which to describe the network topology: the link layer topology, the network layer topology, sometimes referred to generically as the internet topology, and the overlay topology. The Internet topology can itself be seen at four different levels. The first one, the IP interface level, considers IP interfaces of routers and end-systems. Usually, this topology is obtained by using data collected with a probing tool such as traceroute  . The second level, the router level, treats each router as a single node in the topology graph. It can be obtained by aggregating IP interfaces through a technique called alias resolution BIB001 BIB003 BIB005 BIB007 . The point of presence (PoP) level, is a third level, that can be obtained by further aggregating the routers, or directly aggregating the interfaces, that are identified as being geographically co-located. Finally, the AS level provides information about the connectivity of autonomous systems (ASes). This information is not primarily drawn from active measurements, but rather from inter-domain routing information and address databases. However, a deep description of the Internet topology discovery mechanisms is beyond the scope of this article. A typical overlay topology would be the topology of a peer-to-peer system. An overlay topology can be unstructured or structured. Structured overlays are exemplified by distributed hash tables, such as Chord BIB008 or CAN BIB004 . As explained by Stutzbach et al. BIB011 ," peers select neighbors through a predominantly random process. An overlay topology is influenced by peer participation (i.e., join and leave mechanisms) as well as the protocol behavior (i.e., neighbor selection). Characterizing an overlay topology can be done by examining properties of snapshots of the overlay." These snapshots can be gathered using a topology crawler, an engine that queries peers for a list of their neighbors BIB011 BIB015 . As stated by Stutzback et al. BIB015 ,"a deep understanding of the topological characteristics in overlay systems is required to meaningfully simulate and evaluate the actual performance of the proposed search and replication techniques." The overlay topology has drawn the attention of the net-in this article; we are not directly concerned with peer-to-peer systems. Consequently, describing the overlay topology in more detail would be beyond the scope of this survey. Interested readers might refer to the work of Ripeanu et al. BIB006 , Stutzbach et al. BIB015 and Liang et al.  . The link layer topology, the subject of this article, as defined by Breitbart et al. BIB002 , refers to the characterization of the physical connectivity relationships that exist among entities in a communications network. In other words, it is the description of how data link layer devices, switches and bridges, are interconnected and how the different hosts are connected to them. Figure 1 depicts a simple typical Ethernet network. Maintaining an accurate and complete knowledge of the link layer topology is a prerequisite to many critical network management tasks such as network diagnostics and resource management. There is considerable scientific literature devoted to techniques for the discovery of link-layer topology. This research was mainly led by Breitbart et al. BIB002 BIB009 BIB016 , Lowekamp et al. BIB003 , Black et al. BIB010 , Bejerano   , and, more recently, Gobjuka et al. BIB012 BIB013  BIB014 . The rest of the paper is organized as follows. The next section describes the motivation behind discovering topology of Ethernet networks. Section III describes methods used to discover Layer-2 network elements. In Section IV we focus on topology discovery methods presented in the literature. Section V describes limitations and issues related to Data Link topology discovery. Finally, Section VI concludes the paper.