nach oben

Queueing Systems

Erschienen in:

01.04.2015

Optimal design of measurements on queueing systems

verfasst von: Ben M. Parker, Steven Gilmour, John Schormans, Hugo Maruri-Aguilar

Erschienen in: Queueing Systems | Ausgabe 3-4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We examine the optimal design of measurements on queues with particular reference to the M/M/1 queue. Using the statistical theory of design of experiments, we calculate numerically the Fisher information matrix for an estimator of the arrival rate and the service rate to find optimal times to measure the queue when the number of measurements is limited for both interfering and non-interfering measurements. We prove that in the non-interfering case, the optimal design is equally spaced. For the interfering case, optimal designs are not necessarily equally spaced. We compute optimal designs for a variety of queuing situations and give results obtained under the \(D\)- and \(D_s\)-optimality criteria.

Vorheriger Artikel Optimal service rate perturbations of many server queues in heavy traffic

Nächster Artikel Stochastic grey-box modeling of queueing systems: fitting birth-and-death processes to data

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Syst. 25(1), 173–233 (1997)CrossRef

Acharya, S.: On normal approximation for maximum likelihood estimation from single server queues. Queueing Syst. 40(3), 313 (1999)

Aigner, D.: Parameter estimation from cross-sectional observations on an elementary queuing system. Oper. Res. 22(2), 422–428 (1974)CrossRef

Atkinson, A., Donev, A., Tobias, R.: Optimum Experimental Designs, with SAS. Oxford University Press, Oxford (2007)

Baccelli, F., Machiraju, S., Veitch, D., Bolot, J.: The role of PASTA in network measurement. ACM SIGCOMM Comput. Commun. Rev. 36(4), 231–242 (2006)CrossRef

Baccelli, F., Machiraju, S., Veitch, D., Bolot, J.: On optimal probing for delay and loss measurement. In: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pp. 291–302. ACM (2007)

Baccelli, F., Machiraju, S., Veitch, D., Bolot, J.: Probing for loss: the case against probe trains. Commun. Lett. IEEE 15(5), 590–592 (2011)CrossRef

Basawa, I., Bhat, U., Lund, R.: Maximum likelihood estimation for single server queues from waiting time data. Queueing Syst. 24, 155–167 (1997)CrossRef

Basawa, I., Bhat, U., Zhou, J.: Parameter Estimation in Queueing Systems using Partial Information. Technical Report. Ohio State University, Columbus (2006)

10.

Basawa, I., Prabhu, N.: Estimation in single server queues. Nav. Res. Logist. Q. 28(3), 475–487 (1981)CrossRef

11.

Basawa, I., Prabhu, N.: Large sample inference from single server queues. Queueing Syst. Theory Appl. 3(4), 289–304 (1988)CrossRef

12.

Billingsley, P.: Statistical Inference for Markov Processes. The University of Chicago Press, Chicago (1962)

13.

Bodas, S., Shah, D., Wischik, D.: Congestion control meets medium access: throughput, delay, and complexity. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pp. 399–400 (2012)

14.

Chaloner, K., Verdinelli, I.: Bayesian experimental design: a review. Stat. Sci. 10(3), 273–304 (1995)CrossRef

15.

Chen, T.: Parameter estimation for partially observed queues. IEEE Trans. Commun. 42(9), 2730–2739 (1994)CrossRef

16.

Chernoff, H.: Locally optimal designs for estimating parameters. Ann. Math. Stat. 24(4), 586–602 (1953)CrossRef

17.

Clarke, A.: Maximum likelihood estimates in a simple queue. Ann. Math. Stat. 28(4), 1036–1040 (Dec 1957)

18.

Coffman, E., Robert, P., Simatos, F., Tarumi, S., Zussman, G.: A performance analysis of channel fragmentation in dynamic spectrum access systems. Queueing Syst. 71(3), 293–320 (2012)

19.

Grossglauser, M., Tse, D.N.: A time-scale decomposition approach to measurement-based admission control. IEEE/ACM Trans. Netw. 11(4), 550–563 (2003)CrossRef

20.

Jenkins, J.: The relative efficiency of direct and maximum likelihood estimates of mean waiting time in the simple queue M/M/l. J. Appl. Prob. 9(2), 396–403 (1972)CrossRef

21.

Khisti, A., Huitema, C., Dube, A.: Controlling admission of data streams onto a network based on end-to-end measurements. US Patent 7,239,611, 3 July 2007

22.

Kleinrock, L.: Queueing Systems: Theory, vol. 1. John Wiley & Sons Inc, New York (1975)

23.

Lagarias, J.C., Reeds, J.A., Wright, M.H., Wright, P.E.: Convergence properties of the Nelder–Mead simplex method in low dimensions. SIAM J. Optim. 9, 112–147 (1998)CrossRef

24.

Leland, W.E., Taqqu, M.S., Willinger, W., Wilson, D.V.: On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans. Netw. 2(1), 1–15 (1994)CrossRef

25.

Love, S., Pollock, G.S., Goldsack, P., Kirshenbaum, E.R.: System and method for monitoring communication networks using data stream characterization. US Patent 6,904,020, 7 June 2005

26.

27.

Nilsson, M.: Measuring available path capacity using short probe trains. In IEEE Network Operations and Management Symposium (NOMS), pp. 910–913 (2010)

28.

Norros, I.: A storage model with self-similar input. Queueing Syst. 16(3), 387–396 (1994)CrossRef

29.

Pagendam, D., Pollett, P.: Optimal sampling and problematic likelihood functions in a simple population model. Environ. Model. Assess. 14(6), 759–767 (2009)CrossRef

30.

Pagendam, D., Pollett, P.: Robust optimal observation of a metapopulation. Ecol. Model. 221(21), 2521–2525 (2010)CrossRef

31.

Parker, B., Gilmour, S., Schormans, J.: Measurement of packet loss probability by optimal design of packet probing experiments. IET Commun. 3(6), 979 (2009)CrossRef

32.

Parker, B.M., Gilmour, S.G., Schormans, J.A.: Design of experiments for categorical repeated measurements in packet communication networks. Technometrics 53(4), 339–352 (2011)CrossRef

33.

Raiciu, C., Barre, S., Pluntke, C., Greenhalgh, A., Wischik, D., Handley, M.: Improving datacenter performance and robustness with multipath TCP. ACM SIGCOMM Comput. Commun. Rev. 41, 266–277 (2011)CrossRef

34.

Reynolds, J.: The covariance structure of queues and related processes: a survey of recent work. Adv. Appl. Prob. 7(2), 383–415 (1975)CrossRef

35.

Ross, J., Pagendam, D., Pollett, P.: On parameter estimation in population models II: multi-dimensional processes and transient dynamics. Theor. Popul. Biol. 75(2–3), 123–132 (2009)CrossRef

36.

Roughan, M.: Fundamental bounds on the accuracy of network performance measurements. In: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pp. 253–264 (2005)

37.

Roughan, M.: A comparison of poisson and uniform sampling for active measurements. IEEE J. Sel. Areas Commun. 24(12), 2299–2312 (2006)CrossRef

38.

Shah, D., Wischik, D.: Fluid models of congestion collapse in overloaded switched networks. Queueing Syst. 69(2), 121–143 (2011)CrossRef

39.

Shah, D., Wischik, D.: Log-weight scheduling in switched networks. Queueing Syst. 71(1–2), 97–136 (2012)

40.

Spall, J.: Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control. John Wiley & Sons Inc, New Jersey (2003)CrossRef

41.

The ISP Column. The QoS emperor’s wardrobe. http://www.internetsociety.org/publications/isp-column-june-2012-qos-emperors-wardrobe-1 (2012). Accessed 26 Sept 2014

42.

Wolff, R.: Poisson arrivals see time averages. Oper. Res. 30(2), 223–231 (1982)CrossRef

Titel: Optimal design of measurements on queueing systems
verfasst von: Ben M. Parker
Steven Gilmour
John Schormans
Hugo Maruri-Aguilar
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 3-4/2015
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-014-9421-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3-4/2015

Optimal service rate perturbations of many server queues in heavy traffic

Stochastic grey-box modeling of queueing systems: fitting birth-and-death processes to data

A law of iterated logarithm for multiclass queues with preemptive priority service discipline

The stability of the deterministic Skorokhod problem is undecidable

Heavy-traffic asymptotics for networks of parallel queues with Markov-modulated service speeds