Large Scale Graph Monitoring Or Why an Ant Moving on a Manifold Can Help in Overall Internet Security

The monitoring of large dynamic networks is a major challenge for a wide range of applications. The complexity stems from properties of the underlying graphs, in which slight local changes can lead to sizable variations of global properties, e.g., under certain conditions, a single link cut that may be overlooked during monitoring can result in splitting the graph into two disconnected components. Moreover, it is often difficult to determine whether a change will propagate globally or remain local. In this presentation, we tackle the problem of real-time monitoring of dynamic large scale graphs by developing a geometric approach that leverages concept of Riemannian and differential geometry developed for the proof of Poincarré Theorem. We will illustrate the applications of the developed methods on the practical case of monitoring dynamic variations of global Internet using information provided by combining several BGP feeds. In particular, we use our method to detect major events and changes via the geometry of the embedding of the graph, where a major event is defined as an incident that either impacts a substantial number of prefixes or can be observed by numerous route monitors within a given period of time.