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: Francçois Baccelli , Sridhar Machiraju , Darryl Veitch , Jean C. Bolot, The role of PASTA in network measurement, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
• 3: Francois Baccelli , Sridhar Machiraju , Darryl Veitch , Jean C. Bolot, On optimal probing for delay and loss measurement, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298346]
• 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: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 11: Xiliang Liu , Kaliappa Ravindran , Benyuan Liu , Dmitri Loguinov, Single-hop probing asymptotics in available bandwidth estimation: sample-path analysis, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028831]
• 12: Sridhar Machiraju , Darryl Veitch , François Baccelli , Jean C. Bolot, Adding definition to active probing, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232922]
• 13: Benjamin Melamed , Ward Whitt, On arrivals that see time averages, Operations Research, v.38 n.1, p.156-172, Jan–Feb. 1990 [doi>10.1287/opre.38.1.156]
• 14: Muhammad Mukarram Bin Tariq , Amogh Dhamdhere , Constantinos Dovrolis , Mostafa Ammar, Poisson versus periodic path probing (or, does PASTA matter?), Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.10-10, October 19-21, 2005, Berkeley, CA
• 15: Vern Paxson, End-to-end routing behavior in the Internet, ACM SIGCOMM Computer Communication Review, v.26 n.4, p.25-38, Oct. 1996
• 16: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 17: V. Paxson , G. Almes , J. Mahdavi , M. Mathis, Framework for IP Performance Metrics, RFC Editor, 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: Matthew Roughan, Fundamental bounds on the accuracy of network performance measurements, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 21: Joel Sommers , Paul Barford , Nick Duffield , Amos Ron, Improving accuracy in end-to-end packet loss measurement, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 22: Jacob Strauss , Dina Katabi , Frans Kaashoek, A measurement study of available bandwidth estimation tools, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948211]
• 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: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
active probing, network measurement, nonintrusive mixing arrivals see time averages (NIMASTA), poisson arrivals see time averages (PASTA)