Queuing analysis of polling models

ABSTRACT

A polling model is a system of multiple queues accessed by a single server in cyclic order. Polling models provide performance evaluation criteria for a variety of demand-based, multiple-access schemes in computer and communication systems. This paper presents an overview of the state of the art of polling model analysis, as well as an extensive list of references. In particular, single-buffer systems and infinite-buffer systems with exhaustive, gated, and limited service disciplines are treated. There is also some discussion of systems with a noncyclic order of service and systems with priority. Applications to computer networks are illustrated, and future research topics are suggested.

REFERENCES

• 1: Subhash C. Agrawal , Jeffrey P. Buzen , Ashok K. Thareja, A Unified Approach to Scan Time Analysis of Token Rings and Polling Networks., ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.176-185, August 1984
• 2: ALFORD, M., AND MUNTZ, R. R. 1975. Queueing models for polled multiqueues. In Proceedings of the 4th Texas Conference on Computing Systems, pp. 5B-2.1-2.5.
• 3: AMINETZAH, Y. 1975. An exact approach to the polling system. Ph.D. dissertation, Dept. of Electrical Engineering, McGill Univ., Montreal, Quebec.
• 4: APPLETON, J. M., AND PETERSON, M. M. 1986. Traffic analysis of a token ring PBX. iEEE Trans. Comrnun. COM-34, 5 (May), 417-422.
• 5: ARNDT, K., AND SULANKE, H. 1984. A queueing system with relative and cyclic priorities. Elektron. Inf. Kybern. 20, 7/9 (Sept.), 423-425.
• 6: AVI-ITZHAK, B., MAXWELL, W. L., AND MILLER, L. W. 1965. Queueing with alternating priorities. Oper. Res. 13, 2 (Mar.-Apr.), 306-318.
• 7: Joseph E Baker, Multiple-access communications with prioritized service, University of California at Los Angeles, Los Angeles, CA, 1986
• 8: BAKER, J. E., AND RUBIN, I. 1987. Polling with a general-service order table. IEEE Trans. Commun. COM-35, 3 (Mar.), 283-288. Also in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '86) (Houston, Tex., Dec. 1-4, 1986) pp. 6-11.
• 9: Robert Berry , K. Mani Chandy, Performance models of token ring local area networks, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.266-274, August 29-31, 1983, Minneapolis, Minnesota, United States [doi>10.1145/800040.801414]
• 10: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 11: BHARUCHA-REID, A. T. 1960. Elements of the Theory of Markov Processes and Their Applications. McGraw-Hill, New York.
• 12: Onno J. Boxma, Two Symmmetric Queues with Alternating Service and Switching Times, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.409-431, December 19-21, 1984
• 13: O J Boxma, Models of two queues—a few new views, Proc. of the international seminar on Teletraffic analysis and computer performance evaluation, p.75-98, December 1986, Amsterdam, The Netherlands
• 14: BOXMA, O. J., AND GROENENDIJK, W. P. 1986. Pseudo-conservation laws in cyclic-service systems. Rep. OS-R8606, Centre for Mathematics and Computer Science, Amsterdam.
• 15: BOXMA, O. J., AND GROENENDIJK, W. P. 1987. Two queues with alternating service and switching times. Rep. OS-R8712, Centre for Mathematics and Computer Science, Amsterdam.
• 16: BOXMA, O. J., AND GROENENDIJK, W. P. 1988. Waiting times in discrete-time cyclic-service systems. IEEE Trans. Commun. COM-36, 2 (Feb.), 164-170.
• 17: O. J. Boxma , B. Meister, Waiting-time approximations for cyclic-service systems with switch-over times, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.254-262, May 1986, Raleigh, North Carolina, United States
• 18: O. J. Boxma , B. W. Meister, Waiting-time approximations in multi-queue systems with cyclic service, Performance Evaluation, v.7 n.1, p.59-70, February 1, 1987 [doi>10.1016/0166-5316(87)90057-5]
• 19: Hugh S. Bradlow , Houston F. Byrd, Mean waiting time evaluation of packet switches for centrally controlled PB's, Performance Evaluation, v.7 n.4, p.309-328, Nov. 1987 [doi>10.1016/0166-5316(87)90016-2]
• 20: BRODETSKY, G. L. 1973. Analysis of a model with cyclic servicing of packages of orders. Eng. Cybern. 11, 3, 412-422.
• 21: BRODETSKY, G. L., AND VINNITSKII, V. P. 1973. Some characteristics of systems with cyclic data processing. Cybernetics 9, 3 (May-June), 407-413.
• 22: BUX, W. 1981. Local-area subnetworks: A performance comparison. IEEE Trans. Cornmun. COM- 29, 10 (Oct.), 1465-1473. Reprinted in Advances in Local Area Networks, K. K/Jmmerle, F. A. Tobagi, and J. O. Limb, Eds. IEEE Press, N.Y., 1987, pp. 363-382.
• 23: BUX, W. 1984. Performance issues in local-area networks. IBM Syst. J. 23, 4, 351-374.
• 24: BUX, W. 1987. Modeling token ring networks--A survey. IBM Res. Rep. RZ 1615, IBM Z(irich Research Laboratory, R/Jschlikon, Switzerland.
• 25: BUX, W., AND TRUONG, H. L. 1983. Mean-d~lay approximation for cyclic service queueing systems. Perform. Eval. 3, 3 (Aug.), 187-196. Also, Token-ring performance: Mean-delay approximation, In Proceedings of the lOth international Teletraffic Congress, pp. 3.3.3-1-3.3.3-7.
• 26: BUX, W., CLOSS, F. H., KUEMMERLE, K., KELLER, H. J., AND MUELLER, I-I. R. 1983. Architecture and design of a reliable token-ring network. IEEE J. Selected Areas Cornmun. SAC-l, 5 (Nov.), 756-765. Reprinted in Advances in Local Area Networks, K. K~immerle, F. A. Tobagi, and J. O. Limb, Eds. IEEE Press, N.Y., 1987, pp. 67-80.
• 27: CARSTEN, R. T., AND POSNER, M. J. M. 1978. Simplified statistical models of single and multiple Newhall loops. 1978 National Telecommunications Conference (Birmingham, Ala., Dec. 3-6), pp. 44.5.1-44.5.7, IEEE, New York.
• 28: CARSTEN, R. T., NEWHALL, E. E., AND POSNER, M. J. M. 1977. A simplified analysis of scan times in an asymmetrical Newhall loop with exhaustive service. IEEE Trans. Cornrnun. COM-25, 9 (Sept.), 951-957.
• 29: CHOU, W. 1978. Terminal response time on polled teleprocessing networks. In Proceedings of Computer Network Symposium (Dec.).
• 30: CHU, W. W., AND KONHEIM, A. G. 1972. On the analysis and modeling of a class of computer communication systems, iEEE Trans. Cornmun. COM-20, 3 (June), Part 2, 645-660.
• 31: COFFMAN, E. G. JR., AND GILBERT, E. N. 1986. A continuous polling system with constant service times. IEEE Trans. Inf. Theory IT-33, 4 (July), 584-591.
• 32: E. G. Coffman, Jr. , E. N. Gilbert, Polling and greedy servers on a line, Queueing Systems: Theory and Applications, v.2 n.2, p.115-145, July 1987 [doi>10.1007/BF01158396]
• 33: COFFMAN, E. G., JR., AND HOFRI, M. 1982. On the expected performance of scanning disks. SlAM J. Comput. 11, i (Feb.), 60-70.
• 34: E. G. Coffman, Jr. , M. Hofri, Queueing models of secondary storage devices, Queueing Systems: Theory and Applications, v.1 n.2, p.129-168, Sept. 1986 [doi>10.1007/BF01536186]
• 35: Edward G. Coffman, Jr. , Guy Fayolle , Isi Mitrani, Two Queues with Alternating Service Periods, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.227-239, December 07-09, 1987
• 36: J. W. Cohen, A Two-Queue Model with Semi-Exhaustive Alternating Service, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.19-37, December 07-09, 1987
• 37: COHEN, J. W., AND BOXMA, O. J. 1981. The M/G/1 queue with alternating service formulated as a Riemann-Hilbert problem. In Performance '81, F. J. Kylstra, Ed. North-Holland Publishing Co., Amsterdam, pp. 181-199.
• 38: COHEN, J. W., AND BOXMA, O. J. 1983. Boundary Value Problems in Queueing System Analysis. Mathematics Studies 79. North-Holland Publishing Co., Amsterdam.
• 39: COLVIN, M. A., A~D WEAVER, A. C. 1986. Performance of single access classes on the IEEE 802.4 token bus. IEEE Trans. Commun. COM-34, 12 (Dec.), 1253-1256.
• 40: CONWAY, R. W., MAXWELL, W. L., AND MILLER, L. W. 1967. Theory of Scheduling. Addison- Wesley, Reading, Mass.
• 41: COOPER, R. B. 1970. Queues served in cyclic order: Waiting times. Bell Syst. Tech. Jr. 49, 3 (Mar.), 399-413.
• 42: COOPER, R. B. 1981. Introduction to Queueing Theory. 2d ed. Elsevier North-Holland, New York.
• 43: COOPER, R. B., AND MURRAY, G. 1969. Queues served in cyclic order. Bell Syst. Tech. J. 48, 3 (Mar.), 675-689.
• 44: DARROCH, J. N., NEWELL, G. F., AND MORRIS, R. W. J. 1964. Queues for a vehicle-actuated traffic light. Oper. Res. 12, 6 (Nov.-Dec.), 882-895.
• 45: DAVIES, P., AND GHANI, F. A. 1983. Access protocols for an optical-fibre ring network. Comput. Commun. 6, 4 (Aug.), 185-191.
• 46: DE MORAES, L. F. M. 1981. Message queueing delays in polling schemes with applications to data communication networks. Ph.D. dissertation, UCLA-ENG-8106, Dept. of System Science, School of Engineering and Applied Science, Univ. of California, Los Angeles, Calif.
• 47: DE MORAES, L. F. M. 1987. Comments on "Analysis and applications of a multiqueue cyclic service system with feedback." Tech. Rep., Instituto Militar de Engenharia-RJ, Rio de Janeiro, Brazil.
• 48: DE MORAES, L. F. M., AND RUBIN, I. 1983. On the performance of gated and exhaustive polling under unbalanced traffic. In Proceedings of the iEEE Global Telecommunications Conference (GLOBECOM '83) (San Diego, Calif., Nov 28-Dec. 1). IEEE, New York, pp. 1054-1059.
• 49: DE MORAES, L. F. M., AND RUBIN, i. 1984. Analysis and comparison of message queueing delays in token-rings and token-buses local area networks. In Proceedings of the IEEE International Con{erence on Communications (ICC '84) (Amsterdam, May 14-17). IEEE, New York, pp. 130-135.
• 50: B. T. Doshi, Queueing systems with vacations—a survey, Queueing Systems: Theory and Applications, v.1 n.1, p.29-66, 1986 [doi>10.1007/BF01149327]
• 51: DOU, C., AND CHANG, J.-F. 1987. Polling of two queues with synchronized correlated inputs and zero walktime. In Proceedings of IEEE INFOCOM '87 (San Francisco, Mar. 31-Apr. 2). IEEE, New York, pp. 952-961.
• 52: DUKHOVNYI, I. M. 1969. A single-channel queueing system with alternating priority. Prob. In{. Transrn. 5, 2 (Apr.-June), 47-55.
• 53: DUKHOVNYY, I. M. 1979. An approximate model of motion of urban passenger transportation over annular routes. Eng. Cybern. 17, 1, 161-162.
• 54: EISENBERG, M. 1971. Two queues with changeover times. Oper. Res. 19, 2 (Mar.-Apr.), 386-401.
• 55: EISENBERG, M. 1972. Queues with periodic service and changeover times. Oper. Res. 20, 2 (Mar.-Apr.), 440-451.
• 56: EISENBERG, M. 1979. Two queues with alternating service. SIAM J. Appl. Math. 36, 2 (Apr.), 287-303.
• 57: EVERITT, D. 1986. Simple approximations for token rings. IEEE Trans. Commun. COM-34, 7 (July), 719-721.
• 58: Michael J. Ferguson, Mean waiting time for a token ring with station dependent overheads, Local area and multiple access networks, Computer Science Press, Inc., New York, NY, 1986
• 59: FERGUSON, M. J. 1986b. Computation of the variance of the waiting time for token rings. IEEE J. Selected Areas Commun. SAC-4, 6 (Sept.), 775-782.
• 60: FERGUSON, M. J., AND AMINETZAH, Y. J. 1985. Exact results for nonsymmetric token ring systems. IEEE Trans. Commun. COM-33, 3 (Mar.), 223-231.
• 61: FINE, M., AND TOBAGI, F. A. 1984. Demand assignment multiple access schemes in broadcast bus local area networks. IEEE Trans. Comput. C-33, 12 (Dec.), 1130-1159.
• 62: FISCHER, M. J. 1977. Analysis and design of loop service systems via a diffusion approximation. Oper. Res. 25, 2 (Mar.-Apr.), 269-278.
• 63: FUHRMANN, S. W. 1985. Symmetric queues served in cyclic order. Oper. Res. Lett. 4, 3 (Oct.), 139-144.
• 64: FUHRMANN, S. W. 1987. Inequalities for cyclic service systems with limited service disciplines. In Proceedings of IEEE/IEICE Global Telecommunications Conference 1987 (Tokyo, Nov. 15-18). IEEE, New York, pp. 182-186.
• 65: FUHRMANN, S. W., AND COOPER, R. B. 1985a. Application of decomposition principle in M/G/1 vacation model to two continuum cyclic queueing models--Especially token-ring LANs. A T&T Tech. J. 64, 5 (May-June), 1091-1099.
• 66: FUHRMANN, S. W., AND COOPER, R. B. 1985b. Stochastic decompositions in the M/G/1 queue with generalized vacations. Oper. Res. 33, 5 (Sept.-Oct.), 1117-1129.
• 67: FUHRMANN, S. W., AND WANG, Y. T. 1987. Analysis of cyclic service systems with limited service: Bounds and approximations. Tech. Paper, AT&T Bell Laboratories, Holmdel, N.J.
• 68: Steve W. Fuhrmann , Y. T. Wang, Mean Waiting Time Approximations of Cyclic Service Systems with Limited Service, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.253-265, December 07-09, 1987
• 69: FUKAGAWA, Y., YANARU, T., AND YOSHIDA, $. 1986a. Multiqueues system with controlled and cyclic service. Trans. Inst. Electron. Commun. Eng. Jpn J69-A, 1 (Jan.), 25-31 (in Japanese).
• 70: FUKAGAWA, Y., YANARU, T., AND YOSHIDA, S. 1986b. A cyclic time of multiqueues with priority service rule. Trans. Inst. Electron. Commun. Eng. Jpn J69-A, i (Jan.), 159-160 (in Japanese).
• 71: FUKAGAWA, Y., YANARU, T., AND YOSHIDA, S. 1987. An approximate analysis for a multiqueue with a non-preemptive priority and cyclic service. Trans. Inst. Electron. Inf. Commun. Eng. J70-A, 9 (Sept.), 1351-1354 (in Japanese).
• 72: GERSHT, A. M., AND MARBUKH, V. V. 1975. Queueing systems with readjustment. Eng. Cybern. 13, 4, 55-65.
• 73: GIANINI, J., AND MANFIELD, D. 1988. Cyclic multiqueue systems with two priority classes and exhaustive service. In Data Communication Systems and Their Performance. L. F. M. de Moraes, E. de Souza e Silva and L. F. G. Soares, Eds. Elsevier North-Holland, Amsterdam, pp. 511-526. Perform. Eval. 8, 2 (Apr.), 93-115.
• 74: GOLD, Y. I., AND FRANTA, W. R. 1983. An efficient collision-free protocol for prioritized accesscontrol of cable or radio channels. Comput. Networks 7, 2 83-98.
• 75: GOYAL, A., AND DIAS, D. 1988. Performance of priority protocols on high speed token ring networks. In Data Communication Systems and Their Performance, L. F. M. de Moraes, E. de Souza e Silva, and L. F. G. Soares, Eds. Elsevier North-Holland, Amsterdam, pp. 25-34.
• 76: GROENENDIJK, W. P. 1988. Waiting-time approximations for cyclic-service systems with mixed service strategies. In Proceedings of the 12th International Teletraffic Congress (Torino, Italy).
• 77: HALFIN, S. 1975. An approximate method for calculating delays for a family of cyclic-type queues. Bell Syst. Tech. J. 54, 10 (Dec.), 1733-1754.
• 78: Joseph L. Hammond , Peter P. O'Reilly, Performance analysis of local computer networks, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 79: HASHIDA, O. 1970. Gating multiqueues served in cyclic order. Syst. Comput. Controls 1, 1, 1-8. Also in Trans. Inst. Electron. Commun. Eng. Jpn 53-A, 1 (Jan.), 43-50 (in Japanese).
• 80: HASHIDA, O. 1972. Analysis of multiqueue. Rev. Elect. Commun. Lab. 20, 3-4 (Mar.-Apr.), 189-199.
• 81: HASHIDA, O. 1981. A study of multiqueues in communication control. Ph.D. dissertation, Univ. of Tokyo, Tokyo (in Japanese).
• 82: HASHIDA, O., AND KAWASHIMA, K. 1979. Analysis of a polling system with single user at each terminal. Trans. Inst. Electron. Commun. Eng. Jpn J62-B, 12 (Dec.), 1097-1102 (in Japanese). Also in Rev. Electric. Commun. Lab. 29, 3-4 (Mar.-Apr.), 245-253, 1981.
• 83: HASHIDA, O., AND OHARA, K. 1972. Line accommodation capacity of a communication control unit. Rev. Electr. Commun. Lab. 20, 3-4 (Mar.-Apr.), 231-239.
• 84: HASHIMOTO, K., AND OHMAE, Y. 1986. Performance on the multiple ring networks. Trans. Inf. Process. Soc. Jpn 27, 10 (Oct.), 1003-1010 (in Japanese).
• 85: HAWKES, A. G. 1963. Queueing at traffic intersection. In Proceedings of the 2nd International Symposium on the Theory of Traffic Flow (London).
• 86: HAYES, J. F. 1981. Local distribution in computer communications. IEEE Commun. Mag. 19, 2 (Mar.), 6-14. Also in Advances in Local Area Networks, K. Kiimmerle, F. A. Tobagi, and J. O. Limb, Eds. IEEE Press, New York, 1987, pp. 302-317.
• 87: Jeremiah F. Hayes, Modeling and Analysis of Computer Communications Networks, Perseus Publishing, 1984
• 88: J Hayes , A Jalali Nadushan, Numerical solution to limited service polling models, Computer Communications, v.9 n.4, p.171-176, August 1986 [doi>10.1016/0140-3664(86)90219-7]
• 89: HAYES, J. F., AND SHERMAN, D. N. 1972. A study of data multiplexing techniques and delay performance. Bell Syst. Tech. J. 51, 9 (Nov.), 1983-2011.
• 90: HEYMAN, D. P. 1983. Data-transport performance analysis of Fasnet. Bell Syst. Tech. J. 62, 8 (Oct.), 2547-2560.
• 91: Micha Hofri, Queueing systems with a procrastinating server, ACM SIGMETRICS Performance Evaluation Review, v.14 n.1, p.245-253, May 1986
• 92: M Hofri, Two queues and one server with threshold switching, Proc. of the international seminar on Teletraffic analysis and computer performance evaluation, p.409-428, December 1986, Amsterdam, The Netherlands
• 93: HUMBLET, P. A. 1978. Source coding for communication concentrators. Rep. ESL-R-798, Electronic Systems Laboratory, Massachusetts Institute of Technology, Cambridge, Mass.
• 94: Oliver Ibe, Performance comparison of explicit and implicit token-passing networks, Computer Communications, v.10 n.2, p.59-69, April 1987 [doi>10.1016/0140-3664(87)90102-2]
• 95: IBE, O. C., AND CHEN, P.-Y. 1985. Hybrinet: A hybrid bus and token ring network. Comput. Networks ISDN Syst. 9, 3 (Mar.), 215-221.
• 96: IBE., O. C,, AND CHENG, X. 1986. Analysis of polling systems with single-message buffers. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '86) (Houston, Tex., Dec. 1-4). IEEE, New York, pp. 939-943.
• 97: IISAKU, S., MIKI, N., NAGAI, N., AND HATORI, K. 1980. A consideration of multiqueues with nonexhaustive and cyclic service. Trans. Inst. Electron. Commun. Eng. Jpn J63-B, 11 (Nov.), 1102-1109 (in Japanese).
• 98: IISAKU, S., MIKI, N., NAGAI, N., AND HATORI, K. 1981a. Two queues with alternating service and walking time. Trans. Inst. Electron. Commun. Eng. Jpn J64-B, 4 (Apr.), 342-343 (in Japanese).
• 99: IISAKU, S., MIKI, N., NAGAI, N., AND HATORI, K. 1981b. Relationship of the number of waiting customers to waiting time of multiques with nonexhaustive and cyclic service. Trans. Inst. Electron. Commun. Eng. Jpn J64-B, 8 (Aug.), 891-892 (in Japanese).
• 100: JAISWAL, N. K. 1968. Priority Queues. Academic Press, New York.
• 101: KAMAL, A. E., AND HAMACHER, V, C. 1986. Approximate analysis of non-exhaustive multiserver polling systems with applications to local area networks. Tech. Rep. Dept. of Computing Science, Univ. of Alberta, Edmonton, Alberta, Canada.
• 102: KANADA, Y., AND IKEDA, T. 1987. On a multi-ring local area network. Trans. Inst. Electron. Inf. Commun. Eng. J70-B, 8 (Aug.), 903-911 (in Japanese).
• 103: KARVELAS, D., AND LEON-GARCIA, A. 1986. Performance of integrated packet voice/data tokenpassing rings. IEEE J. Selected Areas Comrnun. SAC-4, 6 (Sept.), 823-832.
• 104: KAYE, A. R. 1972. Analysis of a distributed control loop for data transmission, in Proceedings of the Symposium on Computer-Communications Networks and Teletraffic. Polytechnic Institute of Brooklyn, Brooklyn, N.Y., pp. 47-58.
• 105: KAYE, A. R., AND RICHARDSON, T. G. 1973. A performance criterion and traffic analysis for polling systems. INFOR, Can. J. Oper. Res. Inf. Process. 11, 2 (June), 93-112.
• 106: KIMURA, G., AND TAKAHASHI, Y. 1986. Diffusion approximation for a token ring system with nonexhaustive service. IEEE J. Selected Areas Commun. SAC-4, 6 (Sept.), 794-801.
• 107: KIMURA, G., AND TAKAHASHI, Y. 1987a. Traffic analysis for token ring systems with limited service. Trans. Inst. Electron. In{. Commun. Eng. J70-B, 3 (Mar.), 327-336 (in Japanese).
• 108: KIMURA, G., AND TAKAHASHI, Y. 1987b. An approximation for a token ring system with priority classes of messages. J. Inf. Process. 10, 2, 86-91.
• 109: KLEINROCK, L. 1976. Queueing Systems. Vol. 2, Computer Applications. Wiley, New York.
• 110: KLEINROCK, L., AND SCHOLL, M. O. 1980. Packet switching in radio channels: New conflict-free access schemes. IEEE Trans. Commun. COM-28, 7 (July), 1015-1029.
• 111: KOBAYASHI, H., AND KONHEIM, A. G. 1977. Queueing models for computer communications system analysis. IEEE Trans. Commun. COM-25, i (Jan.), 2-29.
• 112: KONHEIM, A. G. 1976. Chaining in a loop system. IEEE Trans. Commun. COM-24, 2 (Feb.), 203-210.
• 113: KONHEIM, A. G. 1980. Mathematical models for computer data communication. In Case Studies in Mathematical Modeling, W. E. Boyce, Ed. Pitman Advanced Publishing Program, Boston, Mass., pp. 256-334.
• 114: Alan G. Konheim , Bernd Meister, Waiting Lines and Times in a System with Polling, Journal of the ACM (JACM), v.21 n.3, p.470-490, July 1974 [doi>10.1145/321832.321845]
• 115: KRUSKAL, J. B. 1969. Work-scheduling algorithms: A non-probabilistic queueing study (with possible application to No. i ESS). Bell Syst. Tech. J. 48, (Nov.), 2963-2974.
• 116: KSCHISCHANG, F. R., AND MOLLE, M. L. 1987. The helical window token ring. Tech. Rep. Dept. of Electrical Engineering, Univ. of Toronto, Toronto, Canada.
• 117: KUEHN, P. J. 1979. Multiqueue systems with nonexhaustive cyclic service. Bell Syst. Tech. J. 58, 3 (Mar.), 671-698.
• 118: KUEHN, P. J. 1981. Performance of ARQ-protocols for HDX transmission in hierarchical polling systems. Perform. Eval. 1, I (Jan.), 19-30.
• 119: KUROSAWA, K., AND TSUJII, S. 1981. Analysis on asymmetric polling systems with limiting service. in Proceedings of the National Telecommunications Conference 1981 (New Orleans, La., Nov. 29- Dec. 3). IEEE, New York, pp. G.4.2.1-G.4.2.5.
• 120: LAM, S. S. 1983. Multiple access protocols. Computer Communications. Vol. I, Principles, W. Chou, Ed. Prentice Hall, Englewood Cliffs, N.J., pp. 114-155.
• 121: LEE, T. T. 1983. M/G/1/N queue with vacation time and limited service discipline. Tech. Memo. AT&T Bell Laboratories, Holmdel, N.J.
• 122: LEE, T. T. 1984. M/G/1/N Queue with vacation time and exhaustive service discipline. Oper. Res. 32, 4 (Jul.-Aug.), 774-784.
• 123: LEIBOWiTZ, M. A. 1961. An approximate method for treating a class of multiqueue problems. IBM J. Res. Dev. 5, 3 (July), 204-209.
• 124: LEIBOWITZ, M. A. 1962. A note on some fundamental parameters of multiqueue systems. IBM J. Res. Dev. 6, 4 (Oct.), 470-471.
• 125: LEISOWlTZ, M. A. 1968. Queues. Sci. Am. 219, 2 (Aug.), 96-103.
• 126: Hanoch Levy, Non-uniform structures and synchronization patterns in shared-channel communication networks, 1984
• 127: LEVY, H. 1986. Delay computation and dynamic behavior of nonsymmetric polling systems. Tech. Paper. AT&T Bell Laboratories, Holmdel, N.J.
• 128: MACK, C. 1957. The efficiency of N machines uni-directionally patrolled by one operative when walking time is constant and repair times are variable. J. Roy. Stat. Soc. Series B, 19, 1, 173-178.
• 129: MACK, C., MURPHY, T., AND WEBB, N. L. 1957. The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. J. Roy. Star. Soc. Series B, 19, 1, 166-172.
• 130: MANFIELD, D. R. 1983. Analysis of a pollirig system with priorities. In Proceedings of the iEEE Global Telecommunications Conference (San Diego, Calif., Nov. 28-Dec. 1). IEEE, New York, pp. 1504-1508.
• 131: MANFIELD, D. R. 1985. Analysis of a priority polling system for two-way traffic. IEEE Trans. Commun. COM-33, 9 (Sept.), 1001-1006.
• 132: MAPP, G. E., AND MANFIELD, D. R. 1986. Performance analysis of priority polling systems with complex cycles. In Proceedings of the International Council for Computer Communication 1986, P. Kuehn, Ed. (Munich, Sept.). Elsevier North-Holland, Amsterdam, pp. 583-588.
• 133: James Martin, Design of Real-Time Computer Systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 134: MASE, K. 1977. An approximate method for treating a queueing model of a class of time division multiplexing. Trans. Inst. Electron. Commun. Eng. Jpn. J60-A, 3 (Mar.), 332-333 (in Japanese).
• 135: MILLER, L. W. 1964. Alternating priorities in multiclass queues. Ph.D. dissertation, Dept. of Industrial Engineering, Cornell Univ., Ithaca, N.Y.
• 136: MORRIS, R. J. T., AND WANG, Y. T. 1984. Some results for multi-queue systems with multiple cyclic servers. In Performance of Computer-Communication Systems, H. Rudin and W. Bux, Eds. Elsevier North-Holland, Amsterdam, pp, 245-258.
• 137: MURATA, M., AND TAKAGI, H. 1987a. Two-layer modeling for local area networks. In Proceedings of IEEE INFOCOM '87 (San Francisco, Mar. 31-Apr. 2). IEEE, New York, pp. 132-140.
• 138: MURATA, M., AND TAKAGI, H. 1987b. Performance of token ring networks with a finite capacity bridge. TRL Res. Rep., TR87-0027, IBM Japan, Tokyo.
• 139: NAHMIAS, S., AND ROTttKOPF, M. H. 1984. Stochastic models of internal mail delivery systems. Manage. Sci. 30, 9 (Sept.), 1113-1120.
• 140: NAIR, S. S. 1976. Alternating priority queues with non-zero switch rules. Comput. Oper. Res. 3, 337-346.
• 141: NEUTS, M. F., AND YADIN, M. 1968. The transient behavior of the queue with alternating priorities, with special reference to the waitingtimes. Bull. Soc. Math. Belg. 20, 343-376.
• 142: NISHIDA, T., MURATA, M., MIYAHARA, H., AND TAKASHIMA, K. 1983. Prioritized token passing method in ring-shaped local area networks. In Proceedings of the IEEE international Conference on Communications (ICC '83) (Boston, june 19-22). IEEE, New York, pp. D.2.2.1-D.2.2.6.
• 143: NISHIDA, T., MURATA, M., MIYAHARA, H., AND TAKASHIMA, K. 1986. An approximate analysis of a prioritized token passing method in ring-shaped local area networks. Trans. Inst. Electron. Commun. Eng. Jpn E-69, i (Jan.), 29-39.
• 144: NOGUCHI, K., SHIRATORI, N., AND NOGUCHI, S. 1984. Analysis of a multiqueue with finite buffers. Queueing Theory and Its Applications, Lecture Note 519. Research Institute for Mathematical Science, Kyoto Univ., Kyoto, Japan, pp. 114-136 (in Japanese).
• 145: NOMURA, M., AND TSUKAMOTO, K. 1978. Traffic analysis on polling systems. Trans. Inst. Electron. Commun. Eng. Jpn. J61-B, 7 (July), 600-607 (in Japanese).
• 146: OZAWA, T. 1987a. An analysis for multi-queueing systems with cyclic-service discipline: Models with exhaustive and gated services. IEICE Tech. Rep. The Institute of Electronics, information and Communication Engineers of Japan, Tokyo, pp. 19-24 (in Japanese).
• 147: OZAWA, T. 1987b. Analysis of a single server model with two queues having different service disciplines. Tech. Rep. NTT Electrical Communication Laboratories, Musashino-shi, Tokyo.
• 148: PACK, C. D., AND WHITAKER, B. A. 1976. Multipoint private line (MPL) access delay under several interstation disciplines. IEEE Trans. Commun. COM-24, 3 (Mar.), 339-348.
• 149: PANG, J. W. M. 1985. Mean delay analysis for unidirectional broadcast structures for local area networks. Master's thesis, Dept. of Electrical Engineering, Faculty of Applied Science, Univ. of British Columbia, Vancouver, Canada.
• 150: PANG, J. W. M., AND DONALDSON, R. W. 1986. Approximate delay analysis and results for asymmetric token passing and polling networks. IEEE J. Select. Areas Commun. SAC-4, 6 (Sept.), 783-793.
• 151: PENNY, B. K., AND BAGHDADI, A. A. 1979a. Survey of computer communications loop networks: Part 1. Comput. Commun. 2, 4, 165-180.
• 152: PENNY, B. g., AND BAGHDADI, A. A. 1979b. Survey of computer communications loop networks: Part 2. Comput. Commun. 2, 5, 224-241.
• 153: PITTEL, B. G. 1973. Optimal control in a mass service system with several flows of demands. Eng. Cybern. 11, 6, 1029-1044.
• 154: RAITH, T. 1985. Performance analysis of multibus interconnection networks in distributed systems. In 1 lth International Teletraffic Congress, M. Akiyama, Ed. Elsevier North-Holland, Amsterdam, pp. 4.2A-5-1-4.2A-5-7.
• 155: RAITH, T., AND TRAN-GIA, P. 1986. Performance analysis of polling mechanisms with receiver blocking. In Proceedings o{ the International Council {or Computer Communication 1986, P. Kuehn, Ed. (Munich). Elsevier North-Holland, Amsterdam, pp. 577-582.
• 156: REGO, V. J. 1985. Cycle-time distributions in an adaptive token-passing bus network. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '85) (New Orleans, La., Dec. 2-5). IEEE, New York, p. 48.2.
• 157: V Rego, A comparison of two token-passing bus protocols, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.58-66, August 05-07, 1986, Stowe, Vermont, United States
• 158: REGO, V. J., AND NI, L. M. 1986. Cycle-time distributions in token-passing local networks. Tech. Paper. Dept. of Computer Sciences, Purdue Univ., West Lafayette, Ind.
• 159: REISER, M. 1982. Performance evaluation of data communications systems. Proc. iEEE 70, 2 (Feb.), 171-196.
• 160: ROBILLARD, P. N. 1974. An analysis of a loop switching system with multirank buffers based on the Markov process. IEEE Trans. Commun. COM-22, 11 (Nov.), 1772-1778.
• 161: RUBIN, I., AND DE MORAES, L. F. M. 1983. Message delay analysis for polling and token multipleaccess schemes for local communication networks. IEEE J. Select. Areas Commun. SAC-l, 5 (Nov.), 935-947.
• 162: RUBIN, I., AND ZSAI, Z.-H. 1987a. Performance of random-access reservation schemes using a polling backbone for metropolitan and packet-radio networks. In Proceedings of the IEEE International Conference on Communications '87 (Seattle, Wash., June 7-10). IEEE, New York, pp. 1427-1431.
• 163: RUBIN, I., AND ZSAI, Z.-H. 1987b. Performance of double-tier access-control schemes using a polling backbone for metropolitan and interconnected communication networks. IEEE J. Select. Areas Commun. SAC-5, 9 (Sept.), 1403-1417.
• 164: RUNNENBERG, J. TH. 1957. Machines served by a patrolling operator. Statistische Afdeling Rep. S221 (VP13), Mathematisch Centrum, Amsterdam.
• 165: SAATY, T. L. 1961. Elements of Queueing Theory with Applications. McGraw-Hill, New York. Reprinted by Dover Publications, New York, 1983.
• 166: SARKAR, D., AND ZANGWILL, W. I. 1987. Expected waiting time for nonsymmetric cyclic queueing systems--Exact results and applications. Tech. Paper. AT&T Bell Laboratories, Holmdel, N.J.
• 167: SAYDAM, W., AND SETHI, A. S. 1985. Performance evaluation of voice-data token ring LANs with random priorities. In Proceedings of IEEE INFOCOM '85 (Washington, D.C., Mar.). IEEE, New York, pp. 326-332.
• 168: SCHAY, G. JR., 1962. Approximate methods for a multiqueueing problem. IBM J. Res. Dev. 6, 2 (Apr.), 246-249.
• 169: SCHOLL, M. O. 1976. Multiplexing techniques for data transmission over packet switched radio systems. Tech. Rep. UCLA-ENG-76123. Computer Science Dept., Univ. of California, Los Angeles, Calif.
• 170: SCHOLL, M., AND KLEINROCK, L. 1983. On the M/G/1 queue with rest periods and certain serviceindependent queueing disciplines. Oper. Res. 31, 4 (Jul.-Aug.), 705-719.
• 171: SCHOLL, M., AND POTIER, D. 1978. Finite and infinite source models for communication systems under polling. IRIA Rapport de Recherche 308. Institut de Rescherche en Informatique et en Automatique, Le Chesnay, France.
• 172: Mischa K. Schwartz, Computer Communications Network Design and Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 173: Mischa Schwartz, Telecommunication networks: protocols, modeling and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 174: SERVI, L. D. 1985. Capacity estimation of cyclic queues. IEEE Trans. Commun. COM-33, 3 (Mar.), 279-282.
• 175: SERVI, L. D. 1986. Average delay approximation of M/G/1 cyclic service queues with Bernoulli schedules. IEEE J. Select. Areas Commun. SAC-4, 6 (Sept.), 813-822; correction in SAC-5, 3 (Apr.), p. 547, 1987.
• 176: SETHI, A. S., AND SAYDAM, W. 1985. Performance analysis of token ring local area networks. Comput. Networks ISDN Syst. 9, 3 (Mar.), 191-200.
• 177: K. C. Sevcik , M. J. Johnson, Cycle time properties of the FDDI token ring protocol, IEEE Transactions on Software Engineering, v.13 n.3, p.376-385, March 1987 [doi>10.1109/TSE.1987.233169]
• 178: SHEN, Z., MASUYAMA, S., MURO, S., AND HASEGAWA, T. 1985. Performance evaluation ofprioritized token ring protocols. In 11th International Teletraffic Congress, M. Akiyama, Ed. Elsevier North- Holland, Amsterdam, pp. 4.2A-3-1-4.2A-3-7.
• 179: SKINNER, C. E. 1967. A priority queueing system with server-walking time. Oper. Res. 15, 2 (Mar.-Apr.), 278-285.
• 180: SRINIVASAN, M. M. 1986. An approximation for mean waiting times in cyclic server systems with nonexhaustive service. Tech. Rep. 86-36. Dept. of Industrial and Operations Engineering, Univ. of Michigan, Ann Arbor, Mich.
• 181: SRINIVASAN, M. M., AND LEE, H.-S. 1987. An analysis of a prioritized polling mechanism for cyclic server systems. Tech. Rep. 87-6. Dept. of Industrial and Operations Engineering, Univ. of Michigan, Ann Arbor, Mich.
• 182: SRIVASTAVA, H. M., AND KASHYAP, B. R. K. 1982. Special Functions in Queuing Theory and Related Stochastic Processes. Academic Press, Orlando, Fla.
• 183: STIDHAM, S., JR. 1969. Optimal control of a signalized intersection. Part I: Introduction: Structure of intersection models; Part II: Determining the optimal switching policies; Part III: Descriptive stochastic models. Tech. Reps. 94, 95, and 96, Dept. of Operations Research, Cornell Univ., Ithaca, New York.
• 184: STIDHAM, S. 1972. Regenerative processes in the theory of queues, with applications to the alternating-priority queue. Adv. Appl. Probab. 4/3 (Dec.), 542-577.
• 185: SUDA, T., MIYAHARA, H., AND HASEGAWA, T. 1980. Approximate analysis for a queueing system with probabilistic switching. Trans. Inst. Electron. Comrnun. Eng. Jpn J63-D, i (Jan.), 1-8 (in Japanese).
• 186: G. Boyd Swartz, Polling in a Loop System, Journal of the ACM (JACM), v.27 n.1, p.42-59, Jan. 1980 [doi>10.1145/322169.322174]
• 187: SWARTZ, G. B. 1982. Analysis of a SCAN policy in a gated loop system. In Applied Probability- Computer Science: The Interface, vol. 2, R. L. Disney and T. J. Ott, Eds. Birkh~iuser, Boston, pp. 241-252.
• 188: SYKES, J. S. 1969a. Analytical model of half-duplex interconnections of computers. IEEE Trans. Commun. Technol. COM-17, 2 (Apr.), 235-238.
• 189: SYKES, J. S. 1969b. Analysis of the communications aspects of an inquiry-response system. In AFIPS Conference Proceedings, 1969 Fall Joint Computer Conference, vol. 35 (Las Vegas, Nev., Nov. 18-20). AFIPS Press, Reston, Va., pp. 655-667.
• 190: SYKES, J. S. 1970. Simplified analysis of an alternating-priority queueing model with setup times. Oper. Res. 18, 6 (Nov.-Dec.), 1182-1192.
• 191: SZPANKOWSKI, W. AND REGO, V. 1987. Ultimate stability conditions for some multidimensional distributed systems. Tech. Rep. Dept. of Computer Science, Purdue Univ., West Lafayette, Ind.
• 192: TAKJ, CS, L. 1962. Introduction to the Theory of Queues. Oxford University Press, New York.
• 193: TAKJ, CS, L. 1968. Two queues attended by a single server. Oper. Res. 16, 3 (May-June), 639-650.
• 194: Hideaki Takagi, New Message Waiting Time in a Symmetric Polling System, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.293-302, December 19-21, 1984
• 195: Hideaki Takagi, On the analysis of a symmetric polling system with single-message buffers, Performance Evaluation, v.5 n.3, p.149-157, Aug. 1985 [doi>10.1016/0166-5316(85)90009-4]
• 196: TAKAGI, H. 1985b. Mean message waiting times in symmetric multi-queue systems with cyclic service. Perform. Eva{ 5, 4 (Nov.), 271-277. Also in Proceedings of the IEEE International Conference on Communications 1985 (Chicago, June 23-26). IEEE, New York, pp. 1154-1157.
• 197: Hideaki Takagi, Analysis of polling systems, MIT Press, Cambridge, MA, 1986
• 198: TAKAOI, H. 1987a. Analysis and applications of a multi-queue cyclic service system with feedback. IEEE Trans. Commun. COM-35, 2 (Feb.), 248-250.
• 199: Hideaki Takagi, Exact analysis of round-robin schedulng of services, IBM Journal of Research and Development, v.31 n.4, p.484-488, July 1, 1987
• 200: TAKAOI, H. 1987c. Analysis of polling models with a mix of exhaustive and gated service disciplines. Tech. Rep. Tokyo Research Laboratory, iBM Japan, Tokyo.
• 201: TAKAOI, H. 1987d. Queueing analysis of polling systems with zero switchover times. TRL Res. Rep. TR87-0034. IBM Japan, Tokyo.
• 202: TAKAGI, H., AND MURATA, M. 1986. Queueing analysis of scan-type TDM and polling systems, in Computer Networking and Performance Evaluation, T. Hasegawa, H. Takagi, and Y. Takahashi, Eds. Elsevier North-Holland, Amsterdam, pp. 199-211.
• 203: TAKINE, T., TAKAHASHI, Y., AND HASEGAWA, T. 1986. Performance analysis of a polling system with single buffers and its application to interconnected networks. IEEE J. Selected Areas Commun. SAC-4, 6 (Sept.), 802-812.
• 204: TAKINE, T., TAKAHASHI, Y., AND HASEGAWA, T. 1987a. Analysis of a buffer relaxation polling system with single buffers. In Proceedings of the Seminar on Queueing Theory and Its Applications (Kyoto, Japan, May 11-13). Kyoto Univ., Kyoto, Japan. pp. 117-132.
• 205: TAKINE, T., TAKAHASHI, Y., AND HASEGAWA, T. 1987b. An analysis for interdeparture process of a polling system with single message buffer at each station. Trans. Inst. Electron. Inf. Commun. Eng. 70-B, 9 (Sept.), 989-998.
• 206: TAKINE, T., TAKAHASHI, Y., AND HASEGAWA, T. 1987c. Average message delay of an asymmetric single buffer polling system with round-robin scheduling of services. Tech. Rep. 87020. Dept. of Applied Mathematics and Physics, Kyoto Univ., Kyoto, Japan.
• 207: Tetsuya Takine , Yutaka Takahashi , Toshiharu Hasegawa, Analysis of an Asymmetric Polling System with Single Buffers, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.241-251, December 07-09, 1987
• 208: TOBAGI, F. A., AND FINE, M. 1983. Performance of unidirectional broadcast local area networks: Expressnet and Fasnet. IEEE J. Select. Areas Commun. SAC-I, 5 (Sept.), 913-926.
• 209: TOBAGI, F. A., AND KLEINROCK, L. 1976. Packet switching in radio channels: Part III--Polling and dynamic split-channel reservation multiple channel access. IEEE Trans. Commun. COM-24, 8 (Aug.), 832-845.
• 210: TOBAGI, F. A., BORGONOVO, F., AND FRATTA, L. 1983. Expressnet: A high-performance integratedservices local area network. }EEE J. Selec. Areas Commun. SAC-l, 5 (Sept.), 898-913. Also in Advances in Local Area Networks, K. K~immerle, F. A. Tobagi, and J. O. Limb, Eds. IEEE, New York, 1987, pp. 171-189.
• 211: TRAN-GIA, P. 1988. Discrete-time analysis of polling systems with renewal inputs. In Data Communication Systems and Their Performance, L. F. M. de Moraes, E. de Souza e Silva, and L. F. G. Soares, Eds. Elsevier North-Holland, Amsterdam, pp. 495-510.
• 212: TRAN-GIA, P., ANO RAITH, T. 1986. Multiqueue systems with finite capacity and nonexhaustive cyclic service. In Computer Networking and Performance Evaluation, T. Hasegawa, H. Takagi, and Y. Takahashi, Eds. Elsevier North-Holland, Amsterdam, pp. 213-225.
• 213: Carl Tropper, Local Computer Network Technologies, Academic Press, Inc., Orlando, FL, 1981
• 214: VINNITSKII, V. P., AND BRODETSKII, G. L. 1972. A cyclic queueing system. Cybernetics 8, 6 (Nov.-Dec.), 979-987.
• 215: WANG, D.-G. 1986. Analysis of cyclic service multi-queue systems for ring type local area networks. Master's thesis, Dept. of Electrical and Computer Engineering, North Carolina State Univ., Raleigh, N.C.
• 216: WANO, Y. T., AND MORRIS, R. J. T. 1985. Load sharing in distributed systems. IEEE Trans. Comput. C-34, 3 (Mar.), 204-217.
• 217: Kym Watson, Performance Evaluation of Cyclic Service Strategies - A Survey, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.521-533, December 19-21, 1984
• 218: WOLFF, R. W. 1988. Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs, N.J.
• 219: WU, R. M., AND CHEN, Y.-B. 1975. Analysis of a loop transmission system with round-robin scheduling of services. IBM J. Res. Dev. 19, 5 (Sept.), 486-493.
• 220: YADIN, M. 1970. Queueing with alternating priorities, treated as random walk on the lattice in the plane. J. Appl. Probab. 7, 196-218.
• 221: YAMAMOTO, T., OKADA, H., AND NAKANISHI, Y. 1984. Analysis of token-passing ring networks with transmission priority. Trans. Inst. Electron. Commun. Eng. Jpn., J67-D, 9 (Sept.), 989-996 (in Japanese).
• 222: YUE, O.-C. 1987. Performance of the timed token scheme in MAP. In Proceedings of the IEEE/ IEICE Global Telecommunications Conference 1987. (Tokyo, Nov. 15-18). IEEE, New York, pp. 187-192.
• 223: YUEN, M. L. T., BLACK, B. A., NEWHALL, E. E., AND VENETSANOPOULOS, A. N. 1972. Traffic flow in a distributed lo. op switching system. In Proceedings o{ the Symposium on Computer-Communications Networks and Teletraffic (Apr. 4-6). Polytechnic Institute of Brooklyn, Brooklyn, N.Y., pp. 29-46.
• 224: ZHOANOV, V. S., AND SAKSONOV, E. A. 1979. Conditions of existence of steady-state modes in cyclic queueing systems. Aurora. Remote Control 40, 2, Part I (Feb.), 176-184.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Performance