Blind source separation approach to performance diagnosis and dependency discovery

Abstract

We consider the problem of diagnosing performance problems in distributed system and networks given end-to-end performance measurements provided by test transactions, or probes. Common techniques for problem diagnosis such as, for example, codebook and network tomography usually assume a known dependency (e.g., routing) matrix that describes how each probe depends on the systems components. However, collecting full information about routing and/or probe dependencies on all systems components can be very costly, if not impossible, in large-scale, dynamic networks and distributed systems. We propose an approach to problem diagnosis and dependency discovery from end-to-end performance measurements in cases when the dependency/routing information is unknown or partially known. Our method is based on Blind Source Separation (BSS) approach that aims at reconstructing unobserved input signals and the mixing-weights matrix from the observed mixtures of signals. Particularly, we apply sparse non-negative matrix factorization techniques that appear particularly fitted to the problem of recovering network bottlenecks and dependency (routing) matrix, and show promising experimental results on several realistic network topologies. Copyright 2007 ACM.