Article

On optimal probing for delay and loss measurement

Authors:

Francois Baccelli,

Sridhar Machiraju,

Jean C. BolotAuthors Info & Claims

IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement

Pages 291 - 302

https://doi.org/10.1145/1298306.1298346

Published: 24 October 2007 Publication History

Abstract

Packet delay and loss are two fundamental measures of performance. Using active probing to measure delay and loss typically involves sending Poisson probes, on the basis of the PASTA property (Poisson Arrivals See Time Averages), which ensures that Poisson probing yields unbiased estimates. Recent work, however, has questioned the utility of PASTA for probing and shown that, for delay measurements, i) a wide variety of processes other than Poisson can be used to probe with zero bias and ii) Poisson probing does not necessarily minimize the variance of delay estimates.

In this paper, we determine optimal probing processes that minimize the mean-square error of measurement estimates for both delay and loss. Our contributions are twofold. First, we show that a family of probing processes, specifically Gamma renewal probing processes, has optimal properties in terms of bias and variance. The optimality result is general, and only assumes that the target process we seek to optimally measure via probing, such as a loss or delay process, has a convex auto-covariance function. Second, we use empirical datasets to demonstrate the applicability of our results in practice, specifically to show that the convexity condition holds true and that Gamma probing is indeed superior to Poisson probing. Together, these results lead to explicit guidelines on designing the best probe streams for both delay and loss estimation.

References

[1]

F. Baccelli and P. Bremaud. Elements of Queueing Theory. Springer Verlag, Applications of Mathematics, second edition, 2003.

[2]

F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot. The Role of PASTA in Network Measurement. Computer Communication Review, Proceedings of ACM Sigcomm 2006, 36(4):231--242, 11-15 Sep 2006.

Digital Library

[3]

F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot. Loss Measurement via Probing. Sprint ATL Technical Report No. ATL-020124, February 2007.

[4]

D. Daley and D. Vere-Jones. An Introduction to the Theory of Point Processes. Springer-Verlag, 1988.

[5]

D. Gaver and P. Lewis. First-order autoregressive gamma sequences and point processes. Adv. Appl. Prob., 12:727--745, 1980.

[6]

L. Gradshteyn and L. Ryzhik. Table of Integrals, Series and Products. Academic Press, sixth edition, 2000.

[7]

N. Hohn, D. Veitch, K. Papagiannaki and C. Diot. Bridging router performance and queuing theory. In Proc. of ACM SIGMETRICS'04.

Digital Library

[8]

I. I. P. M. (IPPM). http://www.ietf.org/html.charters/ippm-charter.html, 2005.

[9]

S. Machiraju, D. Veitch, F. Baccelli, and J. Bolot. Adding Definition to Active Probing. In ACM Computer Communication Review, April 2007.

Digital Library

[10]

M. Tariq, A. Dhamdhere, C. Dovrolis, and M. Ammar. Poisson versus Periodic Path Probing (or, Does PASTA Matter)? In ACM Internet Measurement Conf., pages 119--124, Berkeley, CA, Oct 2005.

Digital Library

[11]

T. Ott. The covariance function of the virtual waiting time process in an M/G/1 queue. Adv. App. Prob., 9, 1997.

[12]

D. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi and C. Diot. Analysis of Measured Single-hop Delay from an Operational Backbone Network In Proceedings of IEEE Infocom, June 2002.

[13]

D. Papagiannaki, D. Veitch and N. Hohn. Origins of Microcongestion in an Access Router. In Proceedings of Passive and Active Measurement Conference., 2004.

[14]

V. Paxson. End-to-end routing behavior in the internet. In Proceedings of ACM SIGCOMM, 1997.

Digital Library

[15]

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

Digital Library

[16]

K. Petersen. Ergodic Theory. Cambridge University Press, Cambridge England, 1983.

[17]

M. Roughan. A Comparison of Poisson and Uniform Sampling for Active Measurements. IEEE Journal on Selected Areas in Communication, 24(12):2299--2312, Dec 2006.

[18]

J. Sommers, P. Barford, N. Duffield, and A. Ron. Improving accuracy in end-to-end packet loss measurement. In ACM SIGCOMM'05, pages 157--168, 2005.

Digital Library

[19]

L. Takács. Introduction to the Theory of Queues. Oxford University Press, New York, 1962.

[20]

The Network Simulator - ns-2, 2004. http://www.isi.edu/nsnam/ns/.

[21]

R. Wolff. Poisson Arrivals see Time Averages. Operations Research, 3(2):223--231, 1982.

Digital Library

[22]

Y. Zhang, N. Duffield, and V. Paxson. On the Constancy of Internet Path Properties. In Proceedings of the Internet Measurement Workshop, 2001.

Digital Library

Cited By

Yesmagambetov BMussabekov AAlymov NApsemetov ABalabekova MKayumov KArystanbayev KImanbayeva A(2023)Determination of Characteristics of Associative Storage Devices in Radio Telemetry Systems with Data CompressionComputation10.3390/computation1106011111:6(111)Online publication date: 6-Jun-2023
https://doi.org/10.3390/computation11060111
Mahmood SShahzad M(2023)Per-Flow Packet Loss Measurement without Probing2023 32nd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN58024.2023.10230129(1-10)Online publication date: Jul-2023
https://doi.org/10.1109/ICCCN58024.2023.10230129
WATABE KMURAI NHIRAKAWA SNAKAGAWA K(2022)Accurate Parallel Flow Monitoring for Loss MeasurementsIEICE Transactions on Communications10.1587/transcom.2021EBP3160E105.B:12(1530-1539)Online publication date: 1-Dec-2022
https://doi.org/10.1587/transcom.2021EBP3160
Show More Cited By

Index Terms

On optimal probing for delay and loss measurement
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. General and reference
  1. Cross-computing tools and techniques

Recommendations

The role of PASTA in network measurement
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

Poisson Arrivals See Time Averages (PASTA) is a well known property applicable to many stochastic systems. In active probing, PASTA is invoked to justify the sending of probe packets (or trains) at Poisson times in a variety of contexts. However, due to ...
Determining an adequate probe separation for estimating the arrival rate in an M/D/1 queue using single-packet probing

We present a technique to estimate the arrival rate from delay measurements, acquired using single-packet probing. With practical applications in mind, we investigate a lower bound on the value of probe separation, to obtain a satisfactory estimate in a ...
Convexity Results for the Erlang Delay and Loss Formulae When the Server Utilization Is Held Constant

This paper proves a long-standing conjecture regarding the optimal design of the M/M/s queue. The classical Erlang delay formula is shown to be a convex function of the number of servers when the server utilization is held constant. This means that when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement

October 2007

390 pages

ISBN:9781595939081

DOI:10.1145/1298306

Program Chairs:
Constantine Dovrolis
Georgia Institute of Technology
,
Matthew Roughan
University of Adelaide, Australia

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

IMC07

Sponsor:

IMC07: Internet Measurement Conference

October 24 - 26, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
390
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yesmagambetov BMussabekov AAlymov NApsemetov ABalabekova MKayumov KArystanbayev KImanbayeva A(2023)Determination of Characteristics of Associative Storage Devices in Radio Telemetry Systems with Data CompressionComputation10.3390/computation1106011111:6(111)Online publication date: 6-Jun-2023
https://doi.org/10.3390/computation11060111
Mahmood SShahzad M(2023)Per-Flow Packet Loss Measurement without Probing2023 32nd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN58024.2023.10230129(1-10)Online publication date: Jul-2023
https://doi.org/10.1109/ICCCN58024.2023.10230129
WATABE KMURAI NHIRAKAWA SNAKAGAWA K(2022)Accurate Parallel Flow Monitoring for Loss MeasurementsIEICE Transactions on Communications10.1587/transcom.2021EBP3160E105.B:12(1530-1539)Online publication date: 1-Dec-2022
https://doi.org/10.1587/transcom.2021EBP3160
Chefrour D(2022)One-Way Delay Measurement From Traditional Networks to SDNACM Computing Surveys10.1145/346616754:7(1-35)Online publication date: 30-Sep-2022
https://doi.org/10.1145/3466167
Watabe KMurai NHirakawa SNakagawa K(2019)Accurate Loss Estimation Technique Utilizing Parallel Flow Monitoring2019 15th International Conference on Network and Service Management (CNSM)10.23919/CNSM46954.2019.9012665(1-5)Online publication date: Oct-2019
https://doi.org/10.23919/CNSM46954.2019.9012665
WATABE KHIRAKAWA SNAKAGAWA K(2019)A Parallel Flow Monitoring Technique That Achieves Accurate Delay MeasurementIEICE Transactions on Communications10.1587/transcom.2018EBP3155E102.B:4(865-875)Online publication date: 1-Apr-2019
https://doi.org/10.1587/transcom.2018EBP3155
Shahzad MGanji A(2018)IoTm: A Lightweight Framework for Fine-Grained Measurements of IoT Performance Metrics2018 IEEE 26th International Conference on Network Protocols (ICNP)10.1109/ICNP.2018.00012(12-22)Online publication date: Sep-2018
https://doi.org/10.1109/ICNP.2018.00012
Hark RRicherzhagen NRicherzhagen BRizk ASteinmetz R(2017)Towards an adaptive selection of loss estimation techniques in software-defined networks2017 IFIP Networking Conference (IFIP Networking) and Workshops10.23919/IFIPNetworking.2017.8264838(1-9)Online publication date: Jun-2017
https://doi.org/10.23919/IFIPNetworking.2017.8264838
Watabe KHirakawa SNakagawa K(2017)Accurate delay measurement for parallel monitoring of probe flows2017 13th International Conference on Network and Service Management (CNSM)10.23919/CNSM.2017.8256029(1-9)Online publication date: Nov-2017
https://doi.org/10.23919/CNSM.2017.8256029
WATABE KNAKAGAWA K(2017)Packet Delay Estimation That Transcends a Fundamental Accuracy Bound due to Bias in Active MeasurementsIEICE Transactions on Communications10.1587/transcom.2016EBP3364E100.B:8(1377-1387)Online publication date: 2017
https://doi.org/10.1587/transcom.2016EBP3364
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