1,721,081 research outputs found
Multi-view routing visualization for the identification of BGP issues
No full textThe Internet is constantly evolving and changing over time. Outages, attacks, upgrades, censorships, and policy changes modify the routing very frequently everywhere in the world. To give the possibility to the Internet Service Providers and to the network operators of monitoring such an evolving scenario, many organizations collect information on the routing changes and give free access to them. We propose, prototype, and evaluate a visual interface, called Upstream Visibility, to display such data. It is based on three views: (1) a Global View that, based on stacked area charts, gives the high level trend of the visibility of an IP prefix; (2) a Local View that allows the user to check the effects over time of the visibility of an IP prefix on specific locations of the network; and (3) a traditional graph Animation View. Also, we propose heuristics for producing such type of drawings, evaluating their effectiveness and performance against scenarios describing well-known Internet incidents. Further, we classify Internet issues and study how they are visualized with our interface. We then identify and describe visual patterns which can be used to spot networking issues at a glance
Computing Orthogonal Drawings with the Minimum Number of Bends
No full textWe describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such an algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment with such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further, the experiments show how minimizing the number of bends has positive effects on other quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four
Periodic Path Changes in RIPE Atlas
No full textLarge-scale data sets of the Internet measurements are commonly used by researchers and operators for investigating Internet performance or for tackling network issues. Looking at sequences of traceroutes in such data sets, it is common to observe paths that change over time. We are interested in verifying if there are periodic phenomena affecting such path changes and, if yes, in determining if they depend on artifacts of the used data set or on topology changes of the network. For this purpose, we devise a novel algorithm for detecting periodicities in sequences of traceroutes. Then, we exploit the algorithm for analyzing the traceroutes produced by the RIPE Atlas, a popular public measurement platform. We study and report the features of the found periodicities and some of their causes. We found that: 1) a surprisingly large percentage of the traceroutes exhibit a periodic behavior; 2) a large number of periodicities depend on the RIPE Atlas platform itself; and 3) a smaller amount is related to the MPLS and load balancing
From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-Line Drawings and Morphs
No full textThe algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. Surprisingly, little is known about the resolution of the drawings they produce. In this paper, focusing on maximal plane graphs, we prove tight bounds on the resolution of the planar straight-line drawings produced by Floater’s algorithm, which is a broad generalization of Tutte’s algorithm. Further, we use such a result to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman’s morphing algorithm. Finally, we show that such an algorithm might produce drawings with exponentially-small resolution, even when morphing drawings with polynomial resolution
Upstream visibility: A multi-view routing visualization
No full textThe Internet is constantly evolving and changing over time. Outages, attacks, upgrades, censorships, and policy changes modify the routing very frequently everywhere in the world. To give the possibility to the Internet Service Providers and to the network operators of monitoring such an evolving scenario, many organizations collect the routing changes and give free access to them. We propose, prototype, and evaluate a visual interface, called Upstream Visibility, to display such data. It is based on three views: (1) a global view that, based on stacked area charts, gives the high level trend of the visibility of an IP prefix; (2) a local view allows the user to check the effects over time of the visibility of an IP prefix on specific locations of the network; and (3) a traditional graph animation view. Also, we propose heuristics for producing such type of drawings, evaluating their effectiveness and performance against scenarios describing well-known Internet incidents
Radian: Visual Exploration of Traceroutes
No full textSeveral projects deploy probes in the Internet. Probes are systems that continuously perform traceroutes and other networking measurements (e.g., ping) towards selected targets. Measurements can be stored and analyzed to gain knowledge on several aspects of the Internet, but making sense of such data requires suitable methods and tools for exploration and visualization. We present Radian, a tool that allows to visualize traceroute paths at different levels of detail and to animate their evolution during a selected time interval. We also describe extensive tests of the tool using traceroutes performed by RIPE Atlas Internet probes
Megalos: A scalable architecture for the virtualization of large network scenarios
Full text linkWe introduce an open-source, scalable, and distributed architecture, called Megalos, that supports the implementation of virtual network scenarios consisting of virtual devices (VDs) where each VD may have several Layer 2 interfaces assigned to virtual LANs. We rely on Docker containers to realize vendor-independent VDs and we leverage Kubernetes for the management of the nodes of a distributed cluster. Our architecture does not require platform-specific configurations and supports a seamless interconnection between the virtual environment and the physical one. Also, it guarantees the segregation of each virtual LAN traffic from the traffic of other LANs, from the cluster traffic, and from Internet traffic. Further, a packet is only sent to the cluster node containing the recipient VD. We produce several example applications where we emulate large network scenarios, with thousands of VDs and LANs. Finally, we experimentally show the scalability potential of Megalos by measuring the overhead of the distributed environment and of its signaling protocols
Extending upward planar graph drawings
No full textIn this paper we study the computational complexity of the UPWARD PLANARITY EXTENSION problem, which takes as input an upward planar drawing ΓH of a subgraph H of a directed graph G and asks whether ΓH can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the UPWARD PLANARITY EXTENSION problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the UPWARD PLANARITY EXTENSION problem can be solved in O(nlogn) time if G is an n-vertex upward planar st-graph. This result improves upon a known O(n2)-time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the UPWARD PLANARITY EXTENSION problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in ΓH
Treebar Maps: Schematic Representation of Networks at Scale
No full textMany data sets, crucial for today's applications, consist of enormous networks, containing millions or even billions of elements. Having the possibility of visualizing such networks is of paramount importance. We propose an algorithmic framework and a visual metaphor, dubbed Treebar Maps, to provide schematic representations of huge networks. Our goal is to convey the main features of the network's inner structure in a straightforward, two-dimensional, one-page drawing, that effectively captures the essential quantitative information about the network's main components. Experiments show that we are able to create such representations in a few hundreds of seconds. We demonstrate the metaphor's efficacy through visual examination of extensive graphs, highlighting how their diverse structures are instantly comprehensible via their representations
- …
