Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes

Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Understanding the topology of a network is very important for network control and management. There have been several methods designed for estimating network topology from end-to-end measurements. Among these methods, the maximum-likelihood-based topology inference method is superior to suboptimal and pair-merging approaches, because it is capable of finding the global optimal topology. However, the existing method which searches the maximum likelihood tree directly is time-consuming, and may not be able to obtain the accurate topology of a larger-scale network. To overcome these issues, this study presents a maximum-likelihood-based leaf nodes inserting topology inference method. The method first builds a binary tree with two leaf nodes, and then inserts the remaining nodes into the tree one by one according to the maximum-likelihood criterion. When compared with the previous methods, the proposed method has the advantages of less computational cost and higher estimate precision. The analytical and simulation results show good performances by the proposed method.


    1. 1)
    2. 2)
    3. 3)
    4. 4)
      • Chen, Y., Bindel, D., Katz, R.H.: `Tomography-based overlay network monitoring', Proc. Third ACM SIGCOMM Conf. on Internet Measurement, October 2003, Miami, FL, USA, p. 216–221.
    5. 5)
    6. 6)
    7. 7)
    8. 8)
    9. 9)
      • Chen, A., Cao, J., Bu, T.: `Network tomography: identifiability and Fourier domain estimation', Proc. IEEE INFOCOM 2007, May 2007, Anchorage, AK, USA, p. 1875–1883.
    10. 10)
      • Arya, V., Duffield, N.G., Veitch, D.: `Temporal delay tomography', Proc. IEEE INFOCOM 2008, April 2008, Phoenix, AZ, USA, p. 276–280.
    11. 11)
    12. 12)
      • Lin, Y., Liang, B., Li, B.: `Passive loss inference in wireless sensor networks based on network coding', Proc. IEEE INFOCOM 2009, April 2009, Rio de Janeiro, Brazil, p. 1809–1817.
    13. 13)
      • Ratnasamy, S., McCanne, S.: `Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements', Proc. IEEE INFOCOM 1999, March 1999, New York, USA, p. 353–360.
    14. 14)
      • Duffield, N.G., Horowitz, J., Presti, F.L.: `Adaptive multicast topology inference', Proc. IEEE INFOCOM 2001, April 2001, Anchorage, AK, USA, p. 1636–1645.
    15. 15)
    16. 16)
    17. 17)
    18. 18)
    19. 19)
    20. 20)
      • Ni, J., Xie, H., Tatikonda, S., Yang, Y.R.: `Network routing topology inference from end-to-end measurements', Proc. IEEE INFOCOM 2008, April 2008, Phoenix, AZ, USA, p. 439–447.
    21. 21)
    22. 22)
      • Yogananda, A.P., Murthy, M.N., Gopal, L.: `A fast linear separability test by projection of positive points on subspaces', Proc. 24th Annual Int. Conf. on Machine Learning, June 2007, Corvallis, OR, USA, p. 713–720.
    23. 23)
      •, accessed May 2010.
    24. 24)

Related content

This is a required field
Please enter a valid email address