Visual Analytics of Network Routing Through Traceroute Data: Models and Techniques

Abstract

The Internet has become a fundamental part of our life. Born as a net- work for scienti c purposes, it has grown in size and services to the point to become the backbone of many human daily activities. Studying, shopping, and banking, are examples of activities in which the use of the Internet is nowadays well established. The extraordinary di usion of mobile devices (estimated in 2 billion of connected units in 2016) is greatly contributing in making people use online services. Multimedia services have an increasing importance in this framework, and, in fact, there is a trend in the last years to o er multimedia products over the Internet to the general public. Telephone, music, and movie streaming are examples of this trend, in which names like e.g. Skype, Net ix, Youtube, and Spotify proved to be prominent players. This phenomenon is ad- vantageous for several stakeholders. Content providers can exploit a robust and world-wide distributed network for distributing their contents, easily reaching old and new customers at a fraction of the costs necessary for building and maintaining traditional, dedicated infrastructures. This has a direct impact on customers, who receive more complete services at lower prices. Also, these services are often more interactive than traditional ones, thanks to the digital nature of the Internet, which enables a personalized user experience. Finally, Internet Service Providers (ISPs) are the intermediary in this context. These organizations, traditionally, have developed and hosted the physical networks that run the Internet, and today they see new market opportunities in develop- ing high-performance infrastructures for multimedia Internet services. Internet Service Providers are faced with the challenging task of developing and maintaining networks that increase in size at a dramatic pace but, at the same time, must support multimedia Internet services by providing acceptable performance. In this scenario, metrics are a fundamental tool. Measuring the performance of a network allows for a continuous monitoring, supporting the discovery of faults and the tuning of parameters. ISPs have always used some 1 kind of local monitoring in their networks, for example embedded in routers, which are intermediate devices. However, given the size of modern networks, a local alert raised by a router does not necessarily represent the experience of a user, whose packets traverse long paths in the network. He could have a much worse perception of a fault, because of multiplicative e ects along the path. Or, it could not notice the fault at all, because he is far from it and the e ect on his connection is only negligible. Probe systems are a recent attempt to deal with this problem, and are gathering a growing interest. Such a system distributes small devices called probes across the Internet, which are always connected and continuously perform standard network measurements towards selected targets. Some common measurements that are performed are ping, traceroute, HTTP queries, etc. The results of the measurements are collected in large repositories, which are available for further analysis. The key feature of probes is that they are installed near to real users, often in their houses, hence simulating the actual user experience through the metrics they collect. Among the measurements available in a probe system, traceroute is a stan- dard networking tool that records the path followed by data in the network, from the source to the target. It also records the round-trip time between the source and each intermediate node. Like other standard measurements, it is supported by default by any IP-based network, like the Internet. Di erently from other measurements, traceroute data contain intrinsic topological information, since a traceroute basically represents a path in the network. This means that they can reveal details on the structure of the network, in addition to its performance. At any instant, a protocol decides the routing of the network, which is a set of rules that establish what path is followed by packets to go from a given source to a given destination. In this sense, traceroute is a simple yet e ective tool for sampling the status of the routing at a given instant. If several traceroute paths are merged, the result is the traceroute graph, or routing graph, which represents an approximation of the network topology and of the routing on that network at a given instant. However, the information richness of traceroutes makes them di cult to handle and understand. In fact, most existing tools make only a partial use of traceroutes, showing single paths and the relative round-trip times, without any attempt to process and emphasize the topological information. This underuse can be explained by some challenges, listed in the following, that are encountered when processing traceroutes produced by a probe system. Data Size A large probe system ensures a ne-grained sampling of the Inter- net, but can also produce a humongous amount of data. In fact, thousands of probes can be operating at the same time, performing measurements every few minutes towards a same target for hours or days. The collected data can contain many interesting insights on the network, but transform- ing that large amount of data into useful information for human operators requires automatic processing methods, and suitable visualizations. While this is rather easy for numerical metrics, automatically processing and vi- sualizing in a meaningful way topological data is complex, with the large 2 data size making the task harder. Dynamics Routing is a dynamic entity. It continuously changes as a reaction to network faults or to make an e cient use of the network, i.e. by dis- tributing the load over di erent nodes. Probe systems execute traceroutes periodically, and for this reason produce a sampling of routing dynamics, as a sequence of snapshots. In some sense, dynamics is the most inter- esting aspect of routing, and probe systems give an opportunity to study its evolution. But structured data that change over time are hard to pro- cess and represent. In particular, dynamic graphs are known to be very challenging to visualize in an e ective way. Relation To Metrics Routing changes require to be correlated to metrics to be understood. Indeed, if the path between two nodes as captured by two consecutive traceroutes changed, it is hard to determine the reason for the change without knowing how the value of some metric of interest changed at the same moment. Traceroutes are naturally related to the round-trip time delay, but other metrics are possible. While visualizing metrics alone is relatively easy, there is not a consensus on how to e ectively correlate numerical values with topological data in a dynamic setting. Relation To Geography Traceroutes intrinsically contain geographical infor- mation. Each node of a traceroute is represented with an IP addresses, which can be roughly mapped to a geographical position by means of heuristics. This relationship to geography is interesting for data analy- sis, since the relative geographical locations of two nodes can in uence the routing between them. But, at the same time, it represents a strong constraint for visualization. Indeed, the most natural and e ective way to display geographical positions is superimposing them on a geographical map, which prevents further optimizations of the visualization. This be- comes critical when positions are relative to nodes of a computer network, since these data are subject to scale problems. For example, a tracer- oute can have its endpoints in two large cities, where nodes are relatively near to each other, and then traverse a long oceanic cable with few inter- mediate nodes. If the path is shown in its full extent in a geographical visualization, the areas near to the endpoints show a lot of visual clutter. On the other hand, if only an endpoint is shown so to reduce the clutter, the global view is lost. As a result of the described problems, nowadays large amounts of traceroutes are collected without their full potential is exploited for data analysis. This thesis has the objective of supporting ISPs in making use of massive traceroute data for managing their networks. The products of the study are interactive tools, that implement novel processing algorithms and visualization metaphors for traceroutes. These tools provide human users with a simpli ed but ex- ible view of data, supporting tasks like network debugging and design. The framework is that of visual analytics, a research eld that combines automated 3 analysis techniques with interactive visualizations for an e ective understand- ing, reasoning and decision making on the basis of very large and complex data sets.