Link identifiability in communication networks with two monitors

We investigate the problem of identifying individual link performance metrics in a communication network by measuring end-to-end metrics of selected paths between monitors, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. In a previous work, we developed an algorithm that places the minimum number of monitors to identify all link metrics. However, even the minimum number can be large in some practical networks (e.g., 60% of all the nodes), suggesting high monitor deployment cost. In this paper, we study the dual problem where given a fixed number of monitors, we want to place them to maximize the number of identifiable link metrics, with concrete results for the case of two monitors. The significance of the two-monitor case is that all the tomographic computation can be performed at the destination monitor without shipping measurements to a central node, thus enabling endhost-based network monitoring. We develop an efficient algorithm to determine all identifiable links in an arbitrary network with a given placement of two monitors, based on which we propose an optimal two-monitor placement algorithm to maximize the number of identifiable links. Our evaluation on real ISP topologies shows that although a large number of monitors is needed to identify all link metrics, we can usually identify a substantial portion (up to 97%) of the links using a single pair of optimally placed monitors.