The role of PASTA in network measurement

Abstract

Poisson Arrivals SeeTimeAverages (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 the diversity of aims and analysis techniques used in active probing, the benefits of Poisson-based measurement, and the utility and role of PASTA, are unclear. Using a combination of rigorous results and carefully constructed examples and counterexamples, we map out the issues involved and argue that PASTA is of very limited use in active probing. In particular, Poisson probes are not unique in their ability to sample without bias. Furthermore, PASTA ignores the issue of estimation variance and the central need for an inversion phase to estimate the quantity of interest based on what is directly observable. We give concrete examples of when Poisson probes should not be used, explain why, and offer initial guidelines on suitable alternative sending processes.

References

1. F. Baccelli and P. Bremaud, Elements of Queueing Theory, 2nd ed. Berlin, Germany: Springer-Verlag, 2003, Applications of Mathematics.
2. F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, "The role of PASTA in network measurement," Comput. Commun. Rev., vol. 36, no. 4, pp. 231-242, 2006.
3. F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, "On optimal probing for delay and loss measurement," in Proc. of ACM SIGCOMM IMC, 2007, pp. 291-302.
4. D. R. Cox, Long-Range Dependence: A Review, H. A. David and H. T. David, Eds. Ames, IA: Iowa State Univ. Press, 1984, pp. 55-74.
5. D. J. Daley and D. Vere-Jones, An Introduction to the Theory of Point Processes. New York: Springer-Verlag, 1988.
6. A. Descloux, "On the validity of a particular subscriber's view," in Proc. 5th Int. Teletraffic Cong., New York, 1967, p. 309.
7. D. P. Gaver and P. Lewis, "First-order Autoregressive gamma sequences and point processes," Adv. Appl. Prob., vol. 12, pp. 727-745, 1980.
8. P. Glasserman, Gradient Estimation via Perturbation Analysis . Boston: Kluwer, 1991.
9. "IETF IP Performance Metrics (IPPM)" 2005 {Online}. Available: http://www.ietf.org/html.charters/ippm-charter.html
10. L. Kleinrock, Queueing Systems. New York: Wiley, 1975, vol. I, Theory.
11. X. Liu, K. Ravindran, B. Liu, and D. Loguinov, "Single-hop probing asymptotics in available bandwidth estimation: Sample-path analysis," in Proc. ACM SIGCOMM IMC, 2004, pp. 300-313.
12. S. Machiraju, D. Veitch, F. Baccelli, and J. Bolot, "Adding definition to active probing," Comput. Commun. Rev., vol. 37, no. 2, pp. 17-28, 2007.
13. B. Melamed and W. Whitt, "On arrivals that see time averages," Oper. Res., vol. 38, no. 1, pp. 156-172, 1990.
14. M. Tariq, A. Dhamdhere, C. Dovrolis, and M. Ammar, "Poisson versus periodic path probing (or, Does PASTA Matter)?," in Proc. ACM SIGCOMM IMC, 2005, pp. 317-330.
15. V. Paxson, "End-to-end routing behavior in the Internet," Comput. Commun. Rev., vol. 26, no. 4, pp. 25-38, 1996.
16. V. Paxson, "End-to-end Internet packet dynamics," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 277-292, Jun. 1999.
17. V. Paxson, G. Almes, J. Madhavi, and M. Mathis, "Framework for IP performance metrics," RFC 2330, May 1998.
18. K. Petersen, Ergodic Theory. Cambridge, U.K.: Cambridge Univ. Press, 1983.
19. M. Roughan, "A comparison of poisson and uniform sampling for active measurements," IEEE J. Sel. Areas Commun., vol. 24, no. 12, pp. 2299-2312, Dec. 2006.
20. M. Roughan, "Fundamental bounds on the accuracy of network measurements," in Proc. ACM SIGMETRICS, 2005, pp. 253-264.
21. J. Sommers, P. Barford, N. Duffield, and A. Ron, "Improving accuracy in end-to-end loss measurement," Comput. Commun. Rev., vol. 35, no. 4, pp. 157-168, 2005.
22. J. Strauss, D. Katabi, and F. Kaashoek, "A measurement study of available bandwidth estimation tools," in Proc. ACM SIGCOMM IMC, 2003, pp. 39-44.
23. NS-2 (Network Simulator) ver. 2.27 {Online}. Available: http://www. isi.edu/nsnam/ns/
24. R. Wolff, "Poisson arrivals see time averages," Oper. Res., vol. 30, no. 2, pp. 223-231, 1982.
25. Y. Zhang, N. Duffield, and V. Paxson, "On the constancy of Internet path properties," in Proc. ACM SIGCOMM.IMW, 2001, pp. 197-211.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

    • Metrics

    • Performance

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

    • Probabilistic representations

      • Markov networks

    • Stochastic processes

      • Markov processes

• Networks

  • Network protocols

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes