Algorithm for queueing networks with multi-rate traffic

• Autorzy: Iversen V. B. , King-Tim K.
• Języki publikacji: EN

Abstrakty

EN

In this paper we present a new algorithm for evaluating queueing networks with multi-rate traffic. The detailed state space of a node is evaluated by explicit formulæ. We consider reversible nodes with multi-rate traffic and find the state probabilities by taking advantage of local balance. Theory of queueing networks in general, presumes that we have product form between the nodes. Otherwise, we have the state space explosion. Even so, the detailed state space of each node may become very large because there is no product form between chains inside a node. A prerequisite for product form is reversibility which implies that the arrival process and departure process are identical processes, for example state-dependent Poisson processes. This property is equivalent to reversibility. Due to product form, an open network with multi-rate traffic is easy to evaluate by convolution algorithms because the nodes behave as independent nodes. For closed queueing networks with multiple servers in every node and multi-rate services we may apply multidimensional convolution algorithm to aggregate the nodes so that we end up with two nodes, the aggregated node and a single node, for which we can calculate the detailed performance measures.

Słowa kluczowe

EN

multi-rate traffic; queueing networks; reversibility; insensitivity; product form; convolution; algorithm

• Wydawca: Publishing House of Poznan University of Technology
• Czasopismo: Advances in Electronics and Telecommunications
• Rocznik: 2011
• Tom: Vol. 2, no. 3
• Strony: 3--7
• Opis fizyczny: Bibliogr. 14 poz., fig.

Twórcy

autor

Iversen V. B.

• Department of Photonic Engineering Technical University of Denmark, 2800 Kongens Lyngby, Denmark

autor

King-Tim K.

• Department of Electronic Engineering City University of Hong Kong, Hong Kong

Bibliografia

• [1] J. R. Jackson, “Networks of waiting lines,” Operations Research, vol. 5, pp. 518–521, 1957.
• [2] P. J. Burke, “The output of a queueing system,” Operations Research, vol. 4, pp. 699–704, 1956.
• [3] R. R. P. Jackson, “Queueing systems with phase type service,” Operational Research Quarterly, vol. 5, pp. 109–120, 1954.
• [4] J. R. Jackson, “Jobshop–like queueing systems,” Management Science, vol. 10, no. 1, pp. 131–142, 1963.
• [5] L. Kleinrock, Communication nets: Stochastic message flow and delay. McGraw–Hill, 1964, dover Publications 1972.
• [6] F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios, “Open, closed and mixed networks of queues with different classes of customers,” Journal of the ACM, pp. 248–260, Apr. 1975.
• [7] S. S. Lavenberg and M. Reiser, “Mean–value analysis of closed multichain queueing networks,” Journal of the Association for Computing Machinery, vol. 27, pp. 313–322, 1980.
• [8] J. F. C. Kingman, “Markov population processes,” J. Appl. Prob, vol. 6, pp. 1–18, 1969.
• [9] D. J. Sutton, “The application of reversible Markov population processes to teletraffic,” A.T.R., vol. 13, pp. 3–8, 1980.
• [10] T. Bonald and A. Proutière, “Insensitive bandwidth sharing in data networks,” Queueing Systems, vol. 44, pp. 69–100, 2003.
• [11] T. Bonald and J. Virtamo, “A recursive formula for multirate systems with elastic traffic,” IEEE Commun. Lett., vol. 9, pp. 752–755, Aug. 2005.
• [12] R. Serfozo, Introduction to Stochastic Networks. Springer, Applications of Mathematics, 1999.
• [13] V. B. Iversen, “Reversible fair scheduling: the teletraffic theory revisited,” Springer Lecture Notes on Computer Science, vol. LNCS 4516, pp. 1135–1148, 2007, 20th International Teletraffic Congress, Ottawa, Canada.
• [14] E. Iliakis and G. Kardaras, “Resource allocation in next generation internet,” Master’s thesis, Technical University of Denmark, 2007.