An optimal service policy for buffer systems

ABSTRACT

Consider a switching component in a packet-switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing ports according to a service policy. One requirement in the design of such a system is to determine the buffer storage necessary at the input of each channel and the policy for serving these buffers that will prevent buffer overflow and the corresponding loss of messages. In this paper, a class of buffer service policies, called Least Time to Reach Bound (LTRB), is introduced that guarantees no overflow, and for which the buffer size required at each input channel is independent of the number of channels and their relative speeds. Further, the storage requirement is only twice the maximal length of a message in all cases, and as a consequence the class is shown to be optimal in the sense that any nonoverflowing policy requires at least as much storage as LTRB.

REFERENCES

• 1: ~ANICK, D., MITRA, D., AND SONDHI, M. M. 1982. Stochastic theory of a data-handling system ~with multiple sources. Bell Syst. Tech. J. 61, 8 (Oct.), 1871-1894.
• 2: ~BIRMAN, m., CHANG, P. C., CHEN, J. S. C., AND GUERIN, R. 1989. Buffer sizing in an ISDN frame ~relay switch. IBM Res. Rep. RC14836. IBM Thomas J. Watson Research Center, Yorktown ~Heights, N.Y.
• 3: ~CIDON, I., GOPAL, I., GROVER, G., AND SIDI, M. 1988. Real time packet switching: A perfor- ~mance analysis. IEEE J. Sel. Areas Commun. SAC-6, (Dec.), 1576-1586.
• 4: COHEN, J. W. 1969. The Single Server Queue. North-Holland, Amsterdam, The Netherlands.
• 5: COHEN, J. W. 1974. Superimposed renewal processes and storage with gradual input. Stochast. ~Proc. Their Appl. 2, 31-58.
• 6: ~CRUZ, R. L. 1991. A calculus for network delay, Part I: network elements in isolation. IEEE ~Trans. Inf. Theory 37, 1 (Jan.) 114-131.
• 7: H. R. Gail , G. Grover , R. Guérin , S. L. Hantler , Z. Rosberg , M. Sidi, Buffer size requirements under longest queue first, Performance Evaluation, v.18 n.2, p.133-140, Sept. 1993 [doi>10.1016/0166-5316(93)90033-Q]
• 8: ~GAVER, D. P., AND MILLER, R. G. 1962. Limiting distributions for some storage problems. In ~Studies in Applied Probability and Management Science. Arrow, K., Karlin S., and Scarf, H., eds., ~Stanford Univ. Press, Stanford, Calif.
• 9: A. G. Greenberg , N. Madras, How fair is fair queuing, Journal of the ACM (JACM), v.39 n.3, p.568-598, July 1992 [doi>10.1145/146637.146658]
• 10: ~KASP1, H., AND RUBINOVITCH, M. 1975. The stochastic behavior of a buffer with non-identical ~input lines. Stochast. Proc. Their Appl. 3, 73-88.
• 11: ~KmSHNA, A. 1990. Communication with few buffers: Analysis and design. Univ. Illinois Rep. ~UILU-ENG-90-2259. Univ. Illinois, Urbana-Champaign, Ill.
• 12: ~RUBINOVITCH, M. 1973. The output of a buffered data communication system. Stochast. Proc. ~Their Appl. 1,375-382.
• 13: ~SASAKI, G. 1989. Input buffer requirements for round robin polling systems. In Proceedings of ~27th Annual Allerton Conference on Communication, Control, and Computing. Univ. Illinois, ~Urbana-Champaign, IlL, pp. 397-406.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

General Terms:
Algorithms, Design, Performance

Keywords:
buffer overflow, gradual input, multiplexor, parallel queues, service discipline, switch