skip to main content
article

Efficient and dynamic routing topology inference from end-to-end measurements

Published: 01 February 2010 Publication History

Abstract

Inferring the routing topology and link performance from a node to a set of other nodes is an important component in network monitoring and application design. In this paper, we propose a general framework for designing topology inference algorithms based on additive metrics. The framework can flexibly fuse information from multiple measurements to achieve better estimation accuracy. We develop computationally efficient (polynomial-time) topology inference algorithms based on the framework. We prove that the probability of correct topology inference of our algorithms converges to one exponentially fast in the number of probing packets. In particular, for applications where nodes may join or leave frequently such as overlay network construction, application-layer multicast, and peer-to-peer file sharing/streaming, we propose a novel sequential topology inference algorithm that significantly reduces the probing overhead and can efficiently handle node dynamics. We demonstrate the effectiveness of the proposed inference algorithms via Internet experiments.

References

[1]
D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris, "Resilient overlay networks," in Proc. SOSP, Banff, AB, Canada, Oct. 2001, pp. 131-145.
[2]
D. Antonova, A. Krishnamurthy, Z. Ma, and R. Sundaram, "Managing a portfolio of overlay paths," in Proc. NOSSDAV, Kinsale, Ireland, Jun. 2004, pp. 30-35.
[3]
A. Bestavros, J. Byers, and K. Harfoush, "Inference and labeling of metric-induced network topologies," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 628-637.
[4]
J.-C. Bolot, "End-to-end packet delay and loss behavior in the Internet," in Proc. ACM SIGCOMM, San Francisco, CA, Sep. 1993, pp. 189-199.
[5]
P. Buneman, "The recovery of trees from measures of dissimilarity," in Mathematics in the Archaeological and Historical Sciences. Edinburgh, Scotland: Edinburgh Univ. Press, 1971, pp. 387-395.
[6]
R. Caceres, N. G. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal loss characteristics," IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2462-2480, Nov. 1999.
[7]
R. Castro, M. Coates, G. Liang, R. Nowak, and B. Yu, "Network tomography: Recent developments," Statist. Sci., vol. 19, no. 3, pp. 499-517, 2004.
[8]
R. Castro, M. Coates, and R. Nowak, "Likelihood based hierarchical clustering," IEEE Trans. Signal Process., vol. 52, no. 8, pp. 2308-2321, Aug. 2004.
[9]
J. T. Chang, "Full reconstruction of Markov models on evolutionary trees: Identifiability and consistency," Math. Biosci., vol. 137, pp. 51-73, 1996.
[10]
M. Coates and R. Nowak, "Network loss inference using unicast end-to-end measurement," in Proc. ITC Conf. IP Traffic, Model. Manage., Monterey, CA, Sep. 2000, pp. 28-1-28-9.
[11]
M. Coates, A. O. Hero, III, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Process. Mag., vol. 19, no. 3, pp. 47-65, May 2002.
[12]
M. Coates, R. Castro, M. Gadhiok, R. King, Y. Tsang, and R. Nowak, "Maximum likelihood network topology identification from edge-based unicast measurements," in Proc. ACM SIGMETRICS, Jun. 2002, pp. 11-20.
[13]
N. G. Duffield, J. Horowitz, F. L. Presti, and D. Towsley, "Multicast topology inference from End-to-End measurements," Adv. Perform. Anal., vol. 3, pp. 207-226, 2000.
[14]
N. G. Duffield, J. Horowitz, and F. L. Presti, "Adaptive multicast topology inference," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 1636-1645.
[15]
N. G. Duffield, J. Horowitz, F. L. Presti, and D. Towsley, "Multicast topology inference from measured end-to-end loss," IEEE Trans. Inf. Theory, vol. 48, no. 1, pp. 26-45, Jan. 2002.
[16]
N. G. Duffiled, F. Lo Presti, V. Paxson, and D. Towsley, "Network loss tomography using striped unicast probes," IEEE/ACM Trans. Netw., vol. 14, no. 4, pp. 697-710, Aug. 2006.
[17]
O. Gascuel and M. Steel, "Neighbor-joining revealed," Mol. Biol. Evol., vol. 23, no. 11, pp. 1997-2000, 2006.
[18]
J. Hartigan, Clustering Algorithms. New York: Wiley, 1975.
[19]
J. Ni and S. Tatikonda, "A Markov random field approach to multicast-based network inference problems," in Proc. IEEE ISIT, Seattle, WA, Jul. 2006, pp. 2769-2773.
[20]
J. Ni and S. Tatikonda, "Explicit link parameter estimators based on end-to-end measurements," in Proc. Allerton Conf. Commun., Contr., Comput., Monticello, IL, Sep. 2007, pp. 174-181.
[21]
F. L. Presti, N. G. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal delay distributions," IEEE/ACM Trans. Netw., vol. 10, no. 6, pp. 761-775, Dec. 2002.
[22]
S. Ratnasamy and S. McCanne, "Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements," in Proc. IEEE INFOCOM, Mar. 1999, pp. 353-360.
[23]
N. Saitou and M. Nei, "The neighbor-joining method: A new method for reconstruction of phylogenetic trees," Mol. Biol. Evol., vol. 4, no. 4, pp. 406-425, 1987.
[24]
M. Shih and A. O. Hero, III, "Hierarchical inference of unicast network topologies based on End-to-End measurements," IEEE Trans. Signal Process., vol. 55, no. 5, pp. 1708-1718, May 2007.
[25]
J. Sommers and P. Barford, "An active measurement system for shared environments," in Proc. ACM IMC, San Diego, CA, Oct. 2007, pp. 303-314.
[26]
D. Stutzbach and R. Rejaie, "Understanding churn in peer-to-peer networks," in Proc. ACM SIGCOMM Conf. Internet Meas., Rio de Janeiro, Brazil, 2006, pp. 189-202.
[27]
Y. Tsang, M. Coates, and R. Nowak, "Network delay tomography," IEEE Trans. Signal Process., vol. 51, no. 8, pp. 2125-2136, Aug. 2003.
[28]
M. Yajnik, S. Moon, J. Kurose, and D. Towsley, "Measurement and modelling of the temporal dependence in packet loss," in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 345-352.
[29]
B. Yao, R. Viswanathan, F. Chang, and D. Waddington, "Topology inference in the presence of anonymous routers," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 353-363.

Cited By

View all
  • (2023)Optimized Cross-Path Attacks via Adversarial ReconnaissanceProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36267897:3(1-30)Online publication date: 7-Dec-2023
  • (2022)Simultaneous Topology and Loss Tomography via a Modified Theme Dictionary ModelIEEE Transactions on Signal Processing10.1109/TSP.2022.319180770(4239-4251)Online publication date: 1-Jan-2022
  • (2019)Looking Glass of NFV: Inferring the Structure and State of NFV Network from External ObservationsIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737393(1774-1782)Online publication date: 29-Apr-2019
  • Show More Cited By

Index Terms

  1. Efficient and dynamic routing topology inference from end-to-end measurements

          Recommendations

          Comments

          Information & Contributors

          Information

          Published In

          cover image IEEE/ACM Transactions on Networking
          IEEE/ACM Transactions on Networking  Volume 18, Issue 1
          February 2010
          332 pages

          Publisher

          IEEE Press

          Publication History

          Published: 01 February 2010
          Revised: 18 November 2008
          Received: 24 February 2008
          Published in TON Volume 18, Issue 1

          Author Tags

          1. network measurement
          2. network monitoring
          3. network tomography
          4. routing topology inference

          Qualifiers

          • Article

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • Downloads (Last 12 months)1
          • Downloads (Last 6 weeks)1
          Reflects downloads up to 20 Feb 2025

          Other Metrics

          Citations

          Cited By

          View all
          • (2023)Optimized Cross-Path Attacks via Adversarial ReconnaissanceProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36267897:3(1-30)Online publication date: 7-Dec-2023
          • (2022)Simultaneous Topology and Loss Tomography via a Modified Theme Dictionary ModelIEEE Transactions on Signal Processing10.1109/TSP.2022.319180770(4239-4251)Online publication date: 1-Jan-2022
          • (2019)Looking Glass of NFV: Inferring the Structure and State of NFV Network from External ObservationsIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737393(1774-1782)Online publication date: 29-Apr-2019
          • (2018)Network Structure Inference, A SurveyACM Computing Surveys10.1145/315452451:2(1-39)Online publication date: 17-Apr-2018
          • (2017)PathfinderInternational Journal of Parallel Programming10.1007/s10766-016-0469-745:6(1273-1284)Online publication date: 1-Dec-2017
          • (2015)Network Topology Inference With Partial InformationIEEE Transactions on Network and Service Management10.1109/TNSM.2015.245103212:3(406-419)Online publication date: 1-Sep-2015
          • (2015)Graph Based Induction of unresponsive routers in Internet topologiesComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.02.01281:C(178-200)Online publication date: 22-Apr-2015
          • (2014)The overlay scan attackProceedings of the 8th ACM International Conference on Distributed Event-Based Systems10.1145/2611286.2611295(107-117)Online publication date: 26-May-2014
          • (2014)Model-based diagnosis techniques for Internet delay diagnosis with dynamic routingApplied Intelligence10.1007/s10489-013-0514-941:1(167-183)Online publication date: 1-Jul-2014
          • (2012)Efficient network tomography for internet topology discoveryIEEE/ACM Transactions on Networking10.1109/TNET.2011.217574720:3(931-943)Online publication date: 1-Jun-2012
          • Show More Cited By

          View Options

          Login options

          Full Access

          View options

          PDF

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader

          Figures

          Tables

          Media

          Share

          Share

          Share this Publication link

          Share on social media