Maximum likelihood network topology identification from edge-based unicast measurements

M. Coates, R.M. Castro, R. Nowak, M. Gadhiok, R. King, Y. Tsang

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    93 Citations (Scopus)


    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.
    Original languageEnglish
    Title of host publicationProceedings of the International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2002, Marina del Rey, California, USA, June 15-19, 2002)
    PublisherAssociation for Computing Machinery, Inc
    ISBN (Print)1-58113-531-9
    Publication statusPublished - 2002


    Dive into the research topics of 'Maximum likelihood network topology identification from edge-based unicast measurements'. Together they form a unique fingerprint.

    Cite this