Constellation: automated discovery of service and host dependencies in networked systems

In a modern enterprise network of scale, dependencies between hosts and network services are surprisingly complex, typically undocumented, and rarely static. Even though network management and troubleshooting rely on this information, automated discovery and monitoring of these dependencies remains an unsolved problem. In the system we describe in this paper computers on the network cooperate to make this information available to all users of the network. Constellation uses machine learning techniques to infer a network-wide map of the complex relationships between hosts and services using little more than the timings of packet transmission and reception. Statistical hypothesis testing on the resulting models provides a guaranteed confidence level for the accuracy of the result. The system is demonstrated against a substantial packet trace from an enterprise network.