TY - GEN
T1 - Efficient identification of additive link metrics via network tomography
AU - Ma, Liang
AU - He, Ting
AU - Leung, Kin K.
AU - Towsley, Don
AU - Swami, Ananthram
PY - 2013/12/1
Y1 - 2013/12/1
N2 - 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 paper is to develop efficient algorithms for constructing linearly independent measurement paths and calculating link metrics. 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. Our evaluations on both synthetic and real network topologies verify the superior efficiency of the proposed algorithms, which are orders of magnitude faster than benchmark solutions for large networks.
AB - 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 paper is to develop efficient algorithms for constructing linearly independent measurement paths and calculating link metrics. 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. Our evaluations on both synthetic and real network topologies verify the superior efficiency of the proposed algorithms, which are orders of magnitude faster than benchmark solutions for large networks.
UR - http://www.scopus.com/inward/record.url?scp=84893266203&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893266203&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2013.24
DO - 10.1109/ICDCS.2013.24
M3 - Conference contribution
AN - SCOPUS:84893266203
SN - 9780769550008
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 581
EP - 590
BT - Proceedings - 2013 IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013
T2 - 2013 IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013
Y2 - 8 July 2013 through 11 July 2013
ER -