Jump to content

Beneš method

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by OAbot (talk | contribs) at 14:37, 11 April 2020 (Open access bot: doi added to citation with #oabot.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In queueing theory, a discipline within the mathematical theory of probability, Beneš approach[1] or Beneš method[2] is a result for an exact or good approximation to the probability distribution of queue length. It was introduced by Václav E. Beneš in 1963.[3]

The method introduces a quantity referred to as the "virtual waiting time" to define the remaining workload in the queue at any time. This process is a step function which jumps upward with new arrivals to the system and otherwise is linear with negative gradient.[4] By giving a relation for the distribution of unfinished work in terms of the excess work, the difference between arrivals and potential service capacity, it turns a time-dependent virtual waiting time problem into "an integral that, in principle, can be solved."[5]

References

  1. ^ Sivaraman, V.; Chiussi, F. (2000). "Providing end-to-end statistical delay guarantees with earliest deadline first scheduling and per-hop traffic shaping". Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064). Vol. 2. p. 631. doi:10.1109/INFCOM.2000.832237. ISBN 0-7803-5880-5.
  2. ^ Norros, I. (2000). "Queueing Behavior Under Fractional Brownian Traffic". Self-Similar Network Traffic and Performance Evaluation. p. 101. doi:10.1002/047120644X.ch4. ISBN 0471319740.
  3. ^ Beneš, V. E. (1963). General Stochastic Processes in the Theory of Queues. Addison Wesley.
  4. ^ Reich, E. (1964). "Review: Vaclav E. Benes, General Stochastic Processes in the Theory of Queues". The Annals of Mathematical Statistics. 35 (2): 913. doi:10.1214/aoms/1177703602.
  5. ^ Van Mieghem, P. (2006). "General queueing theory". Performance Analysis of Communications Networks and Systems. p. 247. doi:10.1017/CBO9780511616488.014. ISBN 9780511616488.