Beneš method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

  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) 2. p. 631. doi:10.1109/INFCOM.2000.832237. ISBN 0-7803-5880-5.  edit
  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.  edit
  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.  edit
  5. ^ Van Mieghem, P. (2006). "General queueing theory". Performance Analysis of Communications Networks and Systems. p. 247. doi:10.1017/CBO9780511616488.014. ISBN 9780511616488.  edit