Identifiability of link metrics in communication networks: Theory and algorithm designs

Abstract

In this thesis, we investigate the problem of identifying individual link metrics in a communication network from accumulated end-to-end metrics over selected measurement paths, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. We know from linear algebra that all link metrics can be uniquely identified when the number of linearly independent measurement paths equals n, the number of links. It is, however, inefficient to collect measurements from all possible paths, whose number can grow exponentially in n, as the number of useful measurements (from linearly independent paths) is at most n. The aim of this thesis is thus to characterize network identifiability by easily verifiable conditions and develop efficient algorithms for achieving and maximizing network identifiability.

To characterize network identifiability in terms of the network topology and the number/placement of monitors, our main results are: (i) it is generally impossible to identify all the link metrics by using two monitors; (ii) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; (iii) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only allow efficient identifiability tests, but also enable efficient algorithm design for constructing linearly independent paths and computing individual link metrics. Specifically, we show that whenever there exists a set of n linearly independent measurement paths, there must exist a set of three pairwise independent spanning trees. We exploit this property to develop an algorithm that can construct n linearly independent, cycle-free paths between monitors without examining all candidate paths, whose complexity is quadratic in n. A further benefit of the proposed algorithm is that the generated paths satisfy a nested structure that allows linear-time computation of link metrics without explicitly inverting the measurement matrix. Next, we study a complementary problem of how to characterize network partial identifiability when n linearly independent paths cannot be found in a given network, for which we establish an efficient algorithm to determine all identifiable links in an arbitrary network under a given monitor placement. Finally, we investigate a realistic problem of how to place monitors such that the network uncertainty with respect to internal link metrics is minimized. To this end, we first develop efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed minimum monitor placement algorithm achieves identifiability using a much smaller number of monitors than a baseline solution. However, we observe that the complete identification of all link metrics in a network can require a large number of monitors (e.g., 60% of all nodes), even if assuming optimal placement of monitors. Therefore, we then study the problem of placing a given number of monitors (k monitors) to identify the maximum number of link metrics. For this problem, we build a polynomial-time algorithm to incrementally place monitors such that each newly placed monitor maximizes the number of additional identifiable links. The significance of this k-monitor placement algorithm is that it is provable optimal if the network is 2-vertex-connected. For other types of networks, our evaluation on various ISP topologies shows that the proposed k-monitor placement algorithm allows identification for close to the maximum number of links while incurring a much lower complexity than brute-force approaches.