More Web Proxy on the site http://driver.im/

Article

Maximum likelihood network topology identification from edge-based unicast measurements

Authors:

Yolanda TsangAuthors Info & Claims

SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 11 - 20

https://doi.org/10.1145/511334.511337

Published: 01 June 2002 Publication History

Abstract

Network tomography is a process for inferring "internal" link-level delay and loss performance information based on end-to-end (edge) network measurements. These methods require knowledge of the network topology; therefore a first crucial step in the tomography process is topology identification. This paper considers the problem of discovering network topology solely from host-based, unicast measurements, without internal network cooperation. First, we introduce a novel delay-based measurement scheme that does not require clock synchronization, making it more practical than other previous proposals. In contrast to methods that rely on network cooperation, our methodology has the potential to identify layer two elements (provided they are logical topology branching points and induce some measurable delay). Second, we propose a maximum penalized likelihood criterion for topology identification. This is a global optimality criterion, in contrast to other recent proposals for topology identification that employ suboptimal, pair-merging strategies. We develop a novel Markov Chain Monte Carlo (MCMC) procedure for rapid determination of the most likely topologies. The performance of our new probing scheme and identification algorithm is explored through simulation and Internet experiments.

References

[1]

C. Andrieu, A. Doucet, W. Fitzgerald, and J. Peréz. Bayesian computational approaches to model selection. In Nonlinear and Non Gaussian Signal Processing, Cambridge: Newton Institute Series. Cambridge University Press, 2000.

[2]

A. Bestavros, J. Byers, and K. Harfoush. Inference and labeling of metric-induced network topologies. Technical Report BUCS-2001-010, Computer Science Department, Boston University, June 2001.

Digital Library

[3]

R. Cáceres, N. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Trans. Info. Theory, 45(7):2462-2480, November 1999.

Digital Library

[4]

H. Chipman, E. George, and R. McCulloch. Bayesian CART model search (with discussion). J. Am. Stat. Assoc., 93(6):937-960, 1998.

[5]

M. Coates and R. Nowak. Network loss inference using unicast end-to-end measurement. In ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep. 2000.

[6]

M. Coates and R. Nowak. Network delay distribution inference from end-to-end unicast measurement. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., Salt Lake City, UT, May 2001.

[7]

M. Coates and R. Nowak. Sequential Monte Carlo inference of internal delays in nonstationary data networks. IEEE Trans. Signal Processing, 50(2):366-376, Feb. 2002.

Digital Library

[8]

N. Duffield, J. Horowitz, and F. L. Presti. Adaptive multicast topology inference. In Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.

[9]

N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from end-to-end measurements. In ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep. 2000.

[10]

N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from measured end-to-end loss. IEEE Trans. Info. Theory, 48(1):26-45, January 2002.

Digital Library

[11]

N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.

[12]

S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. PAMI, 6(6):721-741, 1984.

Digital Library

[13]

P. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82:711-732, 1995.

[14]

K. Harfoush, A. Bestavros, and J. Byers. Robust identification of shared losses using end-to-end unicast probes. In Proc. IEEE Int. Conf. Network Protocols, Osaka, Japan, Nov. 2000. Errata available as Boston University CS Technical Report 2001-001.

Digital Library

[15]

K. Harfoush, A. Bestavros, and J. Byers. Measuring bottleneck bandwidth of targeted path segments. Technical Report BUCS-2001-016, Computer Science Department, Boston University, July 2001.

Digital Library

[16]

W. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97-109, 1970.

[17]

K. Lai and M. Baker. Measuring link bandwidths using a deterministic model of packet delay. In Proc. ACM SIGCOMM 2000, Stockholm, Sweden, Aug. 2000.

Digital Library

[18]

N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equations of state calculations by fast computing machines. J. Chem. Phys., 21:1087-1091, 1953.

[19]

UCB/LBNL/VINT network simulator ns (version 2). www.isi.edu/nsnam/ns/.

[20]

V. Paxson. End-to-end Internet packet dynamics. IEEE/ACM Trans. Networking, 7(3):277-292, June 1999.

Digital Library

[21]

F. L. Presti, N. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal delay distributions. Technical Report CMPSCI 99-55, University of Massachusetts, 1999.

Digital Library

[22]

S. Ratnasamy and S. McCanne. Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements. In Proceedings of IEEE INFOCOM 1999, New York, NY, March 1999.

[23]

S. Richardson and P. Green. On Bayesian analysis of mixtures with an unknown number of components. J. Roy. Stat. Soc. B, 59:731-792, 1997.

[24]

J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific, Singapore, 1989.

Digital Library

[25]

C. Robert and G. Casella. Monte Carlo Statistical Methods. Springer Verlag Series in Statistics, New York, 1998.

Digital Library

[26]

D. Rubenstein, J. Kurose, and D. Towsley. Detecting shared congestion of flows via end-to-end measurement. In Proc. ACM SIGMETRICS 2000, Santa Clara, CA, June 2000.

Digital Library

Cited By

Huang YLin YHe T(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: 12-Dec-2023
https://doi.org/10.1145/3626789
Smith KJafarpour SSwami ABullo F(2022)Topology Inference With Multivariate Cumulants: The Möbius Inference AlgorithmIEEE/ACM Transactions on Networking10.1109/TNET.2022.316433630:5(2102-2116)Online publication date: Oct-2022
https://doi.org/10.1109/TNET.2022.3164336
Hou TQu ZWang TLu ZLiu Y(2020)ProTO: Proactive Topology Obfuscation Against Adversarial Network Topology InferenceIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155255(1598-1607)Online publication date: Jul-2020
https://doi.org/10.1109/INFOCOM41043.2020.9155255
Show More Cited By

Recommendations

Maximum likelihood network topology identification from edge-based unicast measurements
Measurement and modeling of computer systems

Network tomography is a process for inferring "internal" link-level delay and loss performance information based on end-to-end (edge) network measurements. These methods require knowledge of the network topology; therefore a first crucial step in the ...
Network Topology Inference from End-to-End Unicast Measurements
WAINA '13: Proceedings of the 2013 27th International Conference on Advanced Information Networking and Applications Workshops

Network tomography is the problem of discovering the delay and loss rate of the internal links of a network, assuming the internal nodes are not cooperating. The first step to solving this problem is finding network topology. Well-known tools such as ...
Topology Identification Based on Multiple Source Network Tomography
IIS '09: Proceedings of the 2009 International Conference on Industrial and Information Systems

Without the cooperation of internal nodes, the traceroute-based approaches and the SNMP-based approaches will fail to identify the topology of the work. Meanwhile, network tomography techniques can infer the logical topology of network without the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

June 2002

299 pages

ISBN:1581135319

DOI:10.1145/511334

General Chair:
Richard Muntz
UCLA
,
Program Chairs:
Margaret Martonosi
Princeton University
,
Edmundo de Souza e Silva
UFRJ, Brazil

ACM SIGMETRICS Performance Evaluation Review Volume 30, Issue 1
Measurement and modeling of computer systems
June 2002
286 pages
ISSN:0163-5999
DOI:10.1145/511399
Issue’s Table of Contents

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMETRICS02

Sponsor:

SIGMETRICS

SIGMETRICS02: The International Conference on Measurement and Modeling of Computer Systems.

June 15 - 19, 2002

California, Marina Del Rey

Acceptance Rates

SIGMETRICS '02 Paper Acceptance Rate 23 of 170 submissions, 14%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

133
Total Citations
View Citations
1,205
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)5

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang YLin YHe T(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: 12-Dec-2023
https://doi.org/10.1145/3626789
Smith KJafarpour SSwami ABullo F(2022)Topology Inference With Multivariate Cumulants: The Möbius Inference AlgorithmIEEE/ACM Transactions on Networking10.1109/TNET.2022.316433630:5(2102-2116)Online publication date: Oct-2022
https://doi.org/10.1109/TNET.2022.3164336
Hou TQu ZWang TLu ZLiu Y(2020)ProTO: Proactive Topology Obfuscation Against Adversarial Network Topology InferenceIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155255(1598-1607)Online publication date: Jul-2020
https://doi.org/10.1109/INFOCOM41043.2020.9155255
Kolaczyk ECsárdi GKolaczyk ECsárdi G(2020)Network Topology InferenceStatistical Analysis of Network Data with R10.1007/978-3-030-44129-6_7(115-140)Online publication date: 3-Jun-2020
https://doi.org/10.1007/978-3-030-44129-6_7
Geng YLiu SYin ZNaik APrabhakar BRosenblum MVahdat ALorch JYu M(2019)SIMONProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323280(549-564)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323280
Pan SZhang ZZhang ZZeng DXu RRao Z(2019)General Identifiability Condition for Network Topology Monitoring with Network TomographySensors10.3390/s1919412519:19(4125)Online publication date: 24-Sep-2019
https://doi.org/10.3390/s19194125
Daniel ERohrer ETschorsch F(2019)Map-Z: Exposing the Zcash Network in Times of Transition2019 IEEE 44th Conference on Local Computer Networks (LCN)10.1109/LCN44214.2019.8990796(84-92)Online publication date: Oct-2019
https://doi.org/10.1109/LCN44214.2019.8990796
Gao LLiu XLiu YWang PDeng MZhu QLi H(2019)Measuring road network topology vulnerability by Ricci curvaturePhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2019.121071527(121071)Online publication date: Aug-2019
https://doi.org/10.1016/j.physa.2019.121071
Bowden RVeitch D(2018)Finding the Right Tree: Topology Inference Despite Spatial DependencesIEEE Transactions on Information Theory10.1109/TIT.2017.273977964:6(4594-4609)Online publication date: Jun-2018
https://doi.org/10.1109/TIT.2017.2739779
Qiao Y(2018)Robust Loss Inference in the Presence of Noisy MeasurementsIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486249(738-746)Online publication date: Apr-2018
https://doi.org/10.1109/INFOCOM.2018.8486249
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents