skip to main content
article

A geometric approach to improving active packet loss measurement

Published: 02 April 2008 Publication History

Abstract

Measurement and estimation of packet loss characteristics are challenging due to the relatively rare occurrence and typically short duration of packet loss episodes. While active probe tools are commonly used to measure packet loss on end-to-end paths, there has been little analysis of the accuracy of these tools or their impact on the network. The objective of our study is to understand how to measure packet loss episodes accurately with end-to-end probes. We begin by testing the capability of standard Poisson-modulated end-to-end measurements of loss in a controlled laboratory environment using IP routers and commodity end hosts. Our tests show that loss characteristics reported from such Poisson-modulated probe tools can be quite inaccurate over a range of traffic conditions. Motivated by these observations, we introduce a new algorithm for packet loss measurement that is designed to overcome the deficiencies in standard Poisson-based tools. Specifically, our method entails probe experiments that follow a geometric distribution to 1) enable an explicit trade-off between accuracy and impact on the network, and 2) enable more accurate measurements than standard Poisson probing at the same rate. We evaluate the capabilities of our methodology experimentally by developing and implementing a prototype tool, called BADABING. The experiments demonstrate the trade-offs between impact on the network and measurement accuracy. We show that BADABING reports loss characteristics far more accurately than traditional loss measurement tools.

References

[1]
{1} W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the self-similar nature of Ethernet traffic (extended version)," IEEE/ACM Trans. Networking, vol. 2, no. 1, pp. 1-15, Feb. 1994.
[2]
{2} V. Paxson, "Strategies for sound internet measurement," in Proc. ACM SIGCOMM '04, Taormina, Italy, Nov. 2004.
[3]
{3} R. Wolff, "Poisson arrivals see time averages," Oper. Res., vol. 30, no. 2, Mar.-Apr. 1982.
[4]
{4} G. Almes, S. Kalidindi, and M. Zekauskas, "A one way packet loss metric for IPPM," IETF RFC 2680, Sep. 1999.
[5]
{5} Y. Zhang, N. Duffield, V. Paxson, and S. Shenker, "On the constancy of internet path properties," in Proc. ACM SIGCOMM Internet Measurement Workshop '01, San Francisco, CA, Nov. 2001.
[6]
{6} J. Bolot, "End-to-end packet delay and loss behavior in the internet," in Proc. ACM SIGCOMM '93, San Francisco, CA, Sep. 1993.
[7]
{7} V. Paxson, "End-to-end internet packet dynamics," in Proc. ACM SIGCOMM '97, Cannes, France, Sep. 1997.
[8]
{8} M. Yajnik, S. Moon, J. Kurose, and D. Towsley, "Measurement and modeling of temporal dependence in packet loss," in Proc. IEEE INFOCOM '99, New York, Mar. 1999.
[9]
{9} D. Papagiannaki, R. Cruz, and C. Diot, "Network performance monitoring at small time scales," in Proc. ACM SIGCOMM '03, Miami, FL, Oct. 2003.
[10]
{10} P. Barford and J. Sommers, "Comparing probe-and router-based packet loss measurements," IEEE Internet Computing, Sep./Oct. 2004.
[11]
{11} S. Brumelle, "On the relationship between customer and time averages in queues," J. Appl. Probabil., vol. 8, 1971.
[12]
{12} F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, "The role of PASTA in network measurement," in Proc. ACM SIGCOMM, Pisa, Italy, Sep. 2006.
[13]
{13} S. Alouf, P. Nain, and D. Towsley, "Inferring network characteristics via moment-based estimators," in Proc. IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
[14]
{14} K. Salamatian, B. Baynat, and T. Bugnazet, "Cross traffic estimation by loss process analysis," in Proc. ITC Specialist Seminar on Internet Traffic Engineering and Traffic Management, Wurzburg, Germany, Jul. 2003.
[15]
{15} Merit Internet Performance Measurement and Analysis Project. 1998 {Online}. Available: http://www.nic.merit.edu/ipma/
[16]
{16} Internet Protocol Performance Metrics. 1998 {Online}. Available: http://www.advanced.org/IPPM/index.html
[17]
{17} A. Adams, J. Mahdavi, M. Mathis, and V. Paxson, "Creating a scalable architecture for Internet measurement," IEEE Network, 1998.
[18]
{18} J. Mahdavi, V. Paxson, A. Adams, and M. Mathis, "Creating a scalable architecture for Internet measurement," in Proc. INET '98, Geneva, Switzerland, Jul. 1998.
[19]
{19} S. Savage, "Sting: A tool for measuring one way packet loss," in Proc. IEEE INFOCOM '00, Tel Aviv, Israel, Apr. 2000.
[20]
{20} M. Allman, W. Eddy, and S. Ostermann, "Estimating loss rates with TCP," ACM Perform. Eval. Rev., vol. 31, no. 3, Dec. 2003.
[21]
{21} P. Benko and A. Veres, "A passive method for estimating end-to-end TCP packet loss," in Proc. IEEE Globecom '02, Taipei, Taiwan, Nov. 2002.
[22]
{22} M. Coates and R. Nowak, "Network loss inference using unicast end-to-end measurement," in Proc. ITC Conf. IP Traffic, Measurement and Modeling, Sep. 2000.
[23]
{23} N. Duffield, F. Lo Presti, V. Paxson, and D. Towsley, "Inferring link loss using striped unicast probes," in Proc. IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
[24]
{24} G. Appenzeller, I. Keslassy, and N. McKeown, "Sizing router buffers," in Proc. ACM SIGCOMM, Portland, OR, 2004.
[25]
{25} C. Villamizar and C. Song, "High performance TCP in ASNET," ACM Comput. Commun. Rev., vol. 25, no. 4, Dec. 1994.
[26]
{26} C. Fraleigh, C. Diot, B. Lyles, S. Moon, P. Owezarski, D. Papagiannaki, and F. Tobagi, "Design and deployment of a passive monitoring infrastructure," in Proc. Passive and Active Measurement Workshop, Amsterdam, Apr. 2001.
[27]
{27} NLANR Passive Measurement and Analysis (PMA). 2005 {Online}. Available: http://www.pma.nlanr.net/
[28]
{28} S. Floyd and V. Paxson, "Difficulties in simulating the internet," IEEE/ACM Trans. Networking, vol. 9, no. 4, 2001.
[29]
{29} J. Sommers and P. Barford, "Self-configuring network traffic generation," in Proc. ACM SIGCOMM, 2004.
[30]
{30} A. Tirumala, F. Qin, J. Dugan, J. Ferguson, and K. Gibbs, "Iperf 1.7.0--The TCP/UDP Bandwidth Measurement Tool," 2007 {Online}. Available: http://www.dast.nlanr.net/Projects/Iperf
[31]
{31} M. Schervish, Theory of Statistics. New York: Springer, 1995.
[32]
{32} A. Pasztor and D. Veitch, "PC based precision timing without GPS," in Proc. ACM SIGMETRICS, Marina Del Ray, CA, Jun. 2002.
[33]
{33} L. Zhang, Z. Liu, and C. Xia, "Clock synchronization algorithms for network measurements," in Proc. IEEE INFOCOM, New York, Jun. 2002.

Cited By

View all
  • (2019)RINGLM: A Link-Level Packet Loss Monitoring Solution for Software-Defined NetworksIEEE Journal on Selected Areas in Communications10.1109/JSAC.2019.292706337:8(1703-1720)Online publication date: 5-Aug-2019
  • (2018)A new approach for packet loss measurement of video streaming and its applicationMultimedia Tools and Applications10.1007/s11042-016-3566-077:10(11589-11608)Online publication date: 1-May-2018
  • (2010)Measurement of loss pairs in network pathsProceedings of the 10th ACM SIGCOMM conference on Internet measurement10.1145/1879141.1879154(88-101)Online publication date: 1-Nov-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 2
April 2008
244 pages

Publisher

IEEE Press

Publication History

Published: 02 April 2008
Published in TON Volume 16, Issue 2

Author Tags

  1. BADABING
  2. active measurement
  3. network congestion
  4. network probes
  5. packet loss

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2019)RINGLM: A Link-Level Packet Loss Monitoring Solution for Software-Defined NetworksIEEE Journal on Selected Areas in Communications10.1109/JSAC.2019.292706337:8(1703-1720)Online publication date: 5-Aug-2019
  • (2018)A new approach for packet loss measurement of video streaming and its applicationMultimedia Tools and Applications10.1007/s11042-016-3566-077:10(11589-11608)Online publication date: 1-May-2018
  • (2010)Measurement of loss pairs in network pathsProceedings of the 10th ACM SIGCOMM conference on Internet measurement10.1145/1879141.1879154(88-101)Online publication date: 1-Nov-2010
  • (2010)Multiobjective monitoring for SLA complianceIEEE/ACM Transactions on Networking10.1109/TNET.2009.203197418:2(652-665)Online publication date: 1-Apr-2010
  • (2009)Packet loss estimation of TCP flows based on the delayed ACK mechanismProceedings of the 12th Asia-Pacific network operations and management conference on Management enabling the future internet for changing business and new computing services10.5555/1814002.1814085(540-543)Online publication date: 23-Sep-2009
  • (2007)Accurate and efficient SLA compliance monitoringACM SIGCOMM Computer Communication Review10.1145/1282427.128239437:4(109-120)Online publication date: 27-Aug-2007
  • (2007)Accurate and efficient SLA compliance monitoringProceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications10.1145/1282380.1282394(109-120)Online publication date: 27-Aug-2007
  • (2007)A Framework for Multi-Objective SLA Compliance MonitoringProceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications10.1109/INFCOM.2007.298(2446-2450)Online publication date: 1-May-2007

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