ABSTRACT
In queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium state probabilities, do not exist but some product-forms have been obtained over the years in special cases, using a variety of techniques. We show that the Reversed Compound Agent Theorem (RCAT) can obtain these diverse results in a uniform way by its direct application, so unifying product-forms in networks with and without blocking. New product-forms are also constructed for a type of blocking we call `skipping', where a blocked station sends its output-customers to the queue after the one causing the blocking in that customer's path. Finally, we investigate a novel congestion management scheme for networks of finite-capacity queues in which a station with a full queue transmits signals that delete customers from upstream queues in order to reduce incoming traffic.
- Akyildiz, I.F. Exact analysis of queueing networks with rejection blocking. In Proc. of the 1st Internat. Workshop on Queueing Networks with Blocking (North-Holland, Amsterdam, 1989), H. G. Perros and T. Atliok, Eds., pp. 19--29.Google Scholar
- Balsamo, S., De Nitto Persone', V., and Onvural, R. Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, 2001. Google ScholarDigital Library
- Baskett, F., Chandy, K. M., Muntz, R. R., and Palacios, F. G. Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22, 2 (1975), 248--260. Google ScholarDigital Library
- Coleman, J. L., Henderson, W., and Taylor, P. G. Product form equilibrium distributions and a convolution algorithm for Stochastic Petri nets. Perform. Eval., Elsevier 26 (1996), 159--180. Google ScholarDigital Library
- Gelenbe, E. Product form networks with negative and positive customers. Journal of Applied Prob. 28, 3 (1991), 656--663.Google ScholarCross Ref
- Harrison, P. G. Turning back time in Markovian process algebra. Theoretical Computer Science 290, 3 (January 2003), 1947--1986. Google ScholarDigital Library
- Harrison, P. G. Reversed processes, product forms and a non-product form. Linear Algebra and Its Applications 386 (July 2004), 359--381.Google ScholarCross Ref
- Harrison, P. G., and Lee, T. T. Separable equilibrium state probabilities via time reversal in Markovian process algebra. Theoretical Computer Science 346, 1 (2005), 161--182. Google ScholarDigital Library
- Hordijk, A., and Van Dijk, N. Networks of queues with blocking. In Performance '81 (North Holland, 1981), K. Kylstra, Ed., pp. 51--65.Google Scholar
- Kelly, F. Reversibility and stochastic networks. Wiley, New York, 1979.Google Scholar
- Onvural, R. O. Survey of closed queueing networks with blocking. ACM Comput. Surv. 22, 2 (1990), 83--121. Google ScholarDigital Library
- Perros, H. G. Queueing networks with blocking. Oxford University Press, Inc., New York, NY, USA, 1994. Google ScholarDigital Library
- Pittel, B. Closed exponential networks of queues with saturation: The Jackson-type stationary distribution and its asymptotic analysis. Mathematics of Op. Res. 4, 4 (Nov., 1979), pp. 357--378.Google ScholarDigital Library
Index Terms
- A unifying approach to product-forms in networks with finite capacity constraints
Recommendations
A unifying approach to product-forms in networks with finite capacity constraints
Performance evaluation reviewIn queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium ...
Queueing networks and conditional product-forms
ValueTools '13: Proceedings of the 7th International Conference on Performance Evaluation Methodologies and ToolsProduct-forms are well-known in the community of performance evaluation because they allow the computation of the stationary state probabilities of large models that would otherwise be intractable. Roughly speaking, a product-form model consists of ...
A Finite Capacity Queue with Nonrenewal Input and Exponential Dynamic Group Services
<P>In this article we consider a finite capacity queuing model in which jobs (or customers) arrive according to a nonrenewal process. The jobs are processed by a single server in groups of varying size, between a predetermined threshold value and the ...
Comments