Graph reconstruction from path correlation data. (English) Zbl 1403.05142
Summary: A communication network can be modeled as a directed connected graph with edge weights that characterize performance metrics such as loss and delay. Network tomography aims to infer these edge weights from their pathwise versions measured on a set of intersecting paths between a subset of boundary vertices, and even the underlying graph when this is not known. In particular, temporal correlations between path metrics have been used to infer composite weights on the subpath formed by the path intersection. We call these subpath weights the path correlation data.
In this paper we ask the following question: when can the underlying weighted graph be recovered knowing only the boundary vertices and the path correlation data? We establish necessary and sufficient conditions for a graph to be reconstructible from this information, and describe an algorithm to perform the reconstruction. Subject to our conditions, the result applies to directed graphs with asymmetric edge weights, and accommodates paths arising from asymmetric routing in the underlying communication network. We also describe the relationship between the graph produced by our algorithm and the true graph in the case that our conditions are not satisfied.
In this paper we ask the following question: when can the underlying weighted graph be recovered knowing only the boundary vertices and the path correlation data? We establish necessary and sufficient conditions for a graph to be reconstructible from this information, and describe an algorithm to perform the reconstruction. Subject to our conditions, the result applies to directed graphs with asymmetric edge weights, and accommodates paths arising from asymmetric routing in the underlying communication network. We also describe the relationship between the graph produced by our algorithm and the true graph in the case that our conditions are not satisfied.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C12 | Distance in graphs |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 90B18 | Communication networks in operations research |
Keywords:
network tomography; end-to-end measurement; covariance; logical trees; asymmetric routing; unicast probingReferences:
| [1] | Alon, N.; Caro, Y.; Krasikov, I.; Roditty, Y., Combinatorial reconstruction problems, J. Comb. Theory B, 47, 153-161, (1989) · Zbl 0633.05050 · doi:10.1016/0095-8956(89)90016-6 |
| [2] | Arya, V.; Veitch, D.; Bestak, R., Sparsity without the complexity: loss localisation using tree measurements, Networking, 289-303, (2012), Berlin: Springer, Berlin |
| [3] | Belishev, M. I., Recent progress in the boundary control method, Inverse Problems, 23, R1-R67, (2007) · Zbl 1126.35089 · doi:10.1088/0266-5611/23/5/R01 |
| [4] | Belishev, M. I.; Wada, N., On revealing graph cycles via boundary measurements, Inverse Problems, 25, (2009) · Zbl 1180.35547 · doi:10.1088/0266-5611/25/10/105011 |
| [5] | Berkolaiko, G.; Duffield, N.; Ettehad, M.; Manousakis, K., (2018) |
| [6] | Borcea, L.; Druskin, V.; Mamonov, A. V.; Guevara Vasquez, F., Pyramidal resistor networks for electrical impedance tomography with partial boundary measurements, Inverse Problems, 26, (2010) · Zbl 1201.65016 · doi:10.1088/0266-5611/26/10/105009 |
| [7] | Caceres, R.; Duffield, N. G.; Horowitz, J.; Towsley, D. F., Multicast-based inference of network-internal loss characteristics, IEEE Trans. Inf. Theory, 45, 2462-2480, (1999) · Zbl 0961.94002 · doi:10.1109/18.796384 |
| [8] | Cheney, M.; Isaacson, D.; Newell, J. C., Electrical impedance tomography, SIAM Rev., 41, 85-101, (1999) · Zbl 0927.35130 · doi:10.1137/S0036144598333613 |
| [9] | Chua, D. B.; Kolaczyk, E. D.; Crovella, M., Network kriging, IEEE J. Sel. Areas Commun., 24, 2263-2272, (2006) · doi:10.1109/JSAC.2006.884025 |
| [10] | Chung, F. J.; Gilbert, A. C.; Hoskins, J. G.; Schotland, J. C., Optical tomography on graphs, Inverse Problems, 33, (2017) · Zbl 1368.65084 · doi:10.1088/1361-6420/aa66d1 |
| [11] | Duffield, N. G.; Horowitz, J.; Lo Presti, F.; Towsley, D., Multicast topology inference from measured end-to-end loss, IEEE Trans. Inf. Theory, 48, 26-45, (2002) · Zbl 1059.94050 · doi:10.1109/18.971737 |
| [12] | Duffield, N. G., Network tomography of binary network performance characteristics, IEEE Trans. Inf. Theory, 52, 5373-5388, (2006) · Zbl 1309.94196 · doi:10.1109/TIT.2006.885460 |
| [13] | Duffield, N. G.; Presti, F. L., Network tomography from measured end-to-end delay covariance, IEEE/ACM Trans. Netw., 12, 978-992, (2004) · doi:10.1109/TNET.2004.838612 |
| [14] | Duffield, N. G.; Presti, F. L.; Paxson, V.; Towsley, D. F., Network loss tomography using striped unicast probes, IEEE/ACM Trans. Netw., 14, 697-710, (2006) · doi:10.1109/TNET.2006.880182 |
| [15] | Evans, S. N.; Lanoue, D., Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves, Adv. Appl. Math., 96, 39-75, (2018) · Zbl 1383.05052 · doi:10.1016/j.aam.2018.01.001 |
| [16] | Liang, G.; Yu, B., Maximum pseudo likelihood estimation in network tomography, IEEE Trans. Signal Process., 51, 2043-2053, (2003) · doi:10.1109/TSP.2003.814464 |
| [17] | Singhal, H.; Michailidis, G., Identifiability of flow distributions from link measurements with applications to computer networks, Inverse Problems, 23, 1821-1849, (2007) · Zbl 1311.90027 · doi:10.1088/0266-5611/23/5/004 |
| [18] | Teixeira, R.; Shaikh, A.; Griffin, T.; Rexford, J., Dynamics of hot-potato routing in IP networks, Sigmetrics Perform. Eval. Rev., 32, 307-319, (2004) · doi:10.1145/1012888.1005723 |
| [19] | Vardi, Y., Network tomography: estimating source-destination traffic intensities from link data, J. Am. Stat. Assoc., 91, 365-377, (1996) · Zbl 0871.62103 · doi:10.1080/01621459.1996.10476697 |
| [20] | Yu, B.; Cao, J.; Davis, D.; Vander Wiel, S., Time-varying network tomography: router link data, p 79, (2000) · Zbl 1072.90507 · doi:10.1109/ISIT.2000.866369 |
| [21] | Zhang, Y.; Roughan, M.; Duffield, N.; Greenberg, A., Fast accurate computation of large-scale ip traffic matrices from link loads, 206-217, (2003), New York: ACM, New York · doi:10.1145/781027.781053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
