Expected waiting times in polling systems under priority disciplines.

*(English)*Zbl 0732.60106Summary: We analyse a service system which consists of several queues (stations) polled by a single server in a cyclic order with arbitrary switchover times. Customers from several priority classes arrive into each of the queues according to independent Poisson processes and require arbitrarily distributed service times. We consider the system under various priority service disciplines: head-of-the-line priority limited to one and semi- exhaustive, head-of-the-line priority limited to one with background customers, and global priority limited to one. For the first two disciplines we derive a pseudo conservation law. For the third discipline, we show how to obtain the expected waiting time of a customer from any given priority class. For the last discipline we find the expected waiting time of a customer from the highest priority class. The principal tool for our analysis is the stochastic decomposition law for a single server system with vacations.

##### MSC:

60K25 | Queueing theory (aspects of probability theory) |

90B22 | Queues and service in operations research |

##### Keywords:

polling systems; pseudo conservation law; priority service disciplines; single server system with vacations
PDF
BibTeX
XML
Cite

\textit{L. Fournier} and \textit{Z. Rosberg}, Queueing Syst. 9, No. 4, 419--440 (1991; Zbl 0732.60106)

Full Text:
DOI

##### References:

[1] | Token Ring Access Method, IEEE 802,5 Local Network Standard, IEEE Computer Society, Silver Spring, Maryland (1985). |

[2] | ANSI X3T9.5, FDDI Token Ring Media Access Control, Draft Proposal American National Standard, ANSI X3T9.5/83-16, Revision 8 (1985). |

[3] | O.J. Boxma and W.P. Groenendijk, Pseudo conservation laws in cyclic service systems, J. Appl. Prob. 24 (1987) 949-964. · Zbl 0639.60087 |

[4] | O.J. Boxma and W.P. Groenendijk, Waiting times in discrete cyclic service systems, IEEE Trans. Commun. COM-36 (1988) 164-170. · Zbl 0655.90026 |

[5] | O.J. Boxma and B. Meister, Waiting time approximations for cyclic service systems with switchover times, Perform. Eval. 7 (1987) 299-308. · Zbl 0656.90036 |

[6] | O.J. Boxma, Workloads and waiting times in single-server systems with multiple customer classes, Queueing Systems 5 (1989) 185-214. · Zbl 0681.60098 |

[7] | J.W. Cohen, A two queue model with semi-exhaustive alternating service,Performance ’87, eds. PJ. Courtois and G. Latouche (Elsevier/North-Holland, Amsterdam) pp. 19-37. |

[8] | D. Everitt, Simple approximations for token rings, IEEE Trans. Commun. COM-34 (1986) 719-721. |

[9] | M.J. Ferguson and Y.J. Aminetzah, Exact results for nonsymmetric token ring systems, IEEE Trans. Commun. COM-33 (1985) 223-231. |

[10] | S.W. Fuhrmann and R.B. Cooper, Stochastic decompositions in theM/G/1 queue with generalized vacations, Oper. Res. 33 (1985) 1117-1129. · Zbl 0585.90033 |

[11] | S.W. Fuhrmann and Y.T. Wang, Mean waiting time approximations of cyclic service systems with limited service,Performance ’87, eds. P.J. Courtois and G. Latouche (Elsevier/North-Holland, Amsterdam) pp. 253-265. |

[12] | J. Gianini and D. Manfield, An analysis of symmetric polling systems with two priority classes, Perform. Eval. 8 (1988) 93-115. · Zbl 0636.90035 |

[13] | A. Goyal and D. Dias, Performance of Priority protocols on high speed token ring networks, in:Data Communication Systems and their Performance, eds. L.F.M. de Moraes, E. de Souza e Silva and L.F.G. Soares (Elsevier/North-Holland, Amsterdam) pp. 25-34. |

[14] | O.C. Ibe, Flow control in integrated voice and data local area networks,Infocom 86, pp. 496-502. |

[15] | O. Kella and U. Yechiali, Priorities inM/G/1 queue with server vacations, Naval Res. Log. 35 (1988) 23-34. · Zbl 0638.60105 |

[16] | L. Kleinrock,Queueing Systems, vol. 1 (Wiley, New York, 1975). · Zbl 0334.60045 |

[17] | L. Kleinrock,Queueing Systems, vol. 2 (Wiley, New York, 1976). · Zbl 0361.60082 |

[18] | D.R. Manfield, Analysis of a polling system with priorities,IEEE Global Telecommunications Conf, San Diego, California (1983) pp. 43.4.1-43.4.5. |

[19] | M. Murata and H. Takagi, Mean waiting time in nonpreemptive priorityM/G/1 queues with server switchover times,Teletraffic Analysis and Computer Performance Evaluation, eds. O.J. Boxma, J.W. Cohen and H.C. Tijms (Elsevier Science/North-Holland, 1986) pp. 395-407. |

[20] | M. Murata and H. Takagi, Queueing analysis of nonpreemptive reservation priority discipline, IBM Japan Science Inst. (1986). |

[21] | T. Nishida, M. Murata, H. Miyahara and K. Takashima, Prioritized token passing method in ring-shaped local area networks,IEEE Int. Conf. on Communications, ICC ’83, Boston, MA (1983) pp. D2.2.1?-D2.2.6. |

[22] | J. Paradells-Aspas and V. Casares-Giner, Token passing system with priorities at node level, Dept. of Appl. Math., Barcelona, Spain (October 1989). |

[23] | Z. Shen, S. Masuyama, S. Muro and T. Hasegawa, Performance evaluation of prioritized token ring protocols,11th Int. Teletraffic Congress, ed. M. Akiyama (Elsevier Science/North-Holland, 1985) pp. 4.2A-3-1-4.2A-3-7. |

[24] | H. Takagi, Mean message waiting time in a symmetric polling system,Performance ’84, ed. E. Gelenbe (Elsevier Science/North-Holland, 1984) pp. 293-302. |

[25] | H. Takagi,Analysis of Polling Systems (MIT Press, 1986). · Zbl 0647.01001 |

[26] | K.S. Watson, Performance evaluation of cyclic service strategies ? a survey,Performance ’84, ed. E. Gelenbe (Elsevier Science/North-Holland, 1985) pp. 521-533. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.