Abstract
Link bandwidth is obviously critical for numerous network management tasks. Taking into account the issues of measuring costs and network-wide view for large IP network, a distributed measuring system would be an ideal monitoring architecture for active measuring link bandwidth. In this paper, we address the problem of efficiently measure assignment, which optimizing goal is to reduce the cost of measuring all links bandwidth. We show that this problem is NP-hard and propose an approximation algorithm with approximation ratio 2. The effectiveness of our measuring algorithm is validated by simulations evaluation over a wide range of network topologies.
This work is supported by the National Natural Science Foundation of China under Grant No. 60373023.
Chapter PDF
Similar content being viewed by others
References
Stallings, W.: SNMP, SNMPv2, SNMPv3, and RMON 1 and 2. Addison-Wesley Longman, Inc., Amsterdam (1999)
Cisco Systems: NetFlow Services and Applications, White Paper (1999)
Francis, P., Jamin, S., Paxson, V., Zhang, L., Gryniewicz, D.F., Jin, Y.: An Architecture for a Global Internet Host Distance Estimation Service. In: Proc. IEEE INFOCOM 1999 (1999)
Jamin, S., Jin, C., Jin, Y., Raz, Y., Shavitt, Y., Zhang, L.: On the Placement of Internet Instrumentation. In: Proc. IEEE INFOCOM 2000 (2000)
Bolot, J.C.: End-to-End Packet Delay and Loss Behavior in the Internet. In. Proc. ACM SIGCOMM 1993 (1993)
Lai, K., Baker, M.: Measuring Bandwidth. In: Proc. IEEE INFOCOM 1999 (1999)
Jacobsen, V.: Dynamic Distance Maps of the Internet Paths (April 1997), ftp://ftp.ee.lbl.gov/pathchar
Breitbart, Y., Chan, C.Y., Garofalakis, M., Rastogi, R., Siberschatz, A.: Efficiently Monitoring Bandwidth and Latency in IP Networks. In: Proc. IEEE INFOCOM 2001 (2001)
Prasad, R.S., Murray, M., Dovrolis, C., Claffy, K.: Bandwidth Estimation: Metrics, Measurement Techniques, and Tools. IEEE Network 17(6), 27–35 (2003)
Walz, J., Levine, B.: A Hierachical Multicast Monitoring Scheme. In: Proc. Networked Group Communication 2000 (2000)
Bejerano, Y., Rastogi, R.: Robust Monitoring of Link Delays and Faults in Networks. In: Proc. IEEE INFOCOM 2003 (2003)
Kumar, R., Kaur, J.: Efficient Beacon Placement for Network Tomography. In: Proc. ACM Internet Measurement Conference 2004 (October 2004)
Claffy, K., Monk, T.E., McRobb, D.: Internet Tomography. Nature (January 1999)
Horton, J.D., Lopez-Ortiz, A.: On the Number of Distributed Measurement Points for Network Tomography. In: Proc. ACM SIGCOMM IMC 2003, pp. 204–209 (2003)
Suh, K., Guo, Y., Kurose, J., Towsley, D.: Locating Network Monitors: Complexity, Heuristics, and Coverage. In: Proc. IEEE INFOCOM 2005 (2005)
Adler, M., Bu, T., Sitaraman, R.K., Towsley, D.: Tree Layout for Internal Network Characterizations in Multicast Network. In: Proc. Networked Group Comm. (2001)
Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP Topologies with Rocketfuel. In: Proc. ACM SIGCOMM 2002 (2002)
Nguyen, H.X., Thiran, P.: Active Measurment for Multiple Link Failure Diagnosis in IP Networks. In: Proc. PAM 2004 (April 2004)
Doweny, A.B.: Using Pathchar to Estimate Internet Link Characteristics. In: Proc. ACM SIGCOMM 1999 (September 1999)
CAIDA (October 2002), http://www.caida.org/tools/
Hochbaum, D.S.: Approximation Algorithm for NP-Hard Problems. PWS Publishing Company (1997)
Waxman, B.M.: Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications 6(9), 1617–1622 (1988)
Cai, Z., Yin, J., Liu, F., Liu, X.: Distributed Monitoring Model With Bounded Delay For Evolving Networks. Journal of Software, 11 (2005)
Cai, Z., Zhao, W., Yin, J., Liu, X.: Using Passive Measuring to Calibrate Active Measuring Latency. In: Kim, C. (ed.) ICOIN 2005. LNCS, vol. 3391, pp. 198–206. Springer, Heidelberg (2005)
Cai, Z., Yin, J., Liu, F., Liu, X., Lv, S.: Efficiently Monitoring Link Bandwidth in IP Networks. In: Proc. IEEE GLOBECOM 2005 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 IFIP International Federation for Information Processing
About this paper
Cite this paper
Cai, Z., Yin, J., Liu, F., Liu, X., Lv, S. (2005). Distributed Active Measuring Link Bandwidth in IP Networks. In: Jin, H., Reed, D., Jiang, W. (eds) Network and Parallel Computing. NPC 2005. Lecture Notes in Computer Science, vol 3779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11577188_42
Download citation
DOI: https://doi.org/10.1007/11577188_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29810-6
Online ISBN: 978-3-540-32246-7
eBook Packages: Computer ScienceComputer Science (R0)