On Certain Output-Buffer Management Techniques—A Stochastic Model

ABSTRACT

A queueing-type model is used to analyze the storage requirements of a component of a real-time data entry system. The objectives and criteria of the buffer management procedure are identified and related to the variables of the model. Both infinite and finite buffers are considered. The analysis is done symbolically in part and numerically in part to accommodate input processes that are peculiar to the system. Techniques to obtain overflow probabilities are described in detail. It is shown that creating a pool of storage blocks for all the terminals is a better policy than maintaining a separate buffer for each station. The savings brought about by this policy are remarkably insensitive to the characteristics of the input process.

REFERENCES

• 1: E. G. Coffman, Jr. , Thomas A. Ryan, Jr., A study of storage partitioning using a mathematical model of locality, Communications of the ACM, v.15 n.3, p.185-190, March 1972 [doi>10.1145/361268.361280]
• 2: Donald P. Gaver, Jr. , Peter A. W. Lewis, Probability Models for Buffer Storage Allocation Problems, Journal of the ACM (JACM), v.18 n.2, p.186-198, April 1971 [doi>10.1145/321637.321641]
• 3: KASPI, H, AND RUBINOVrrCH, M The stochastic behawour of a buffer w~th non-~denucal input lines Oper. Res, Statist. and Econ Mimeograph Ser No 148, Faculty of Indust and Manage. Eng, Techmon, IIT, Halfa, July 1974.
• 4: KLIMKO, E M An algorithm for calculating indices m Fa'a dl Bruno's formula BIT 13 (1973), 38-49
• 5: Alan G. Konheim , Bernd Meister, Service in a Loop System, Journal of the ACM (JACM), v.19 n.1, p.92-108, Jan. 1972 [doi>10.1145/321679.321687]
• 6: KOSTEN, L Dynamic behavlour of a multi-entry buffer Advances m Appl Probablhty 8 (June 1976), 243-244 (abstract only)
• 7: NEUTS, M.F. Computer power or the hberatlon of apphed probablhty In Mathematical Methods m Queuemg Theory, A B Clarke, Ed, Lecture Notes m Economics and Mathemaucal Systems 98, Sprlnger-Verlag, New York, 1973
• 8: NF.UTS, M F , AND KLIMKO, E M Computattonal Probabthty (preliminary version).
• 9: SCHWEITZER, P Buffer overflow probabdltles using an mfimte-capacity model Advances zn Appl Probabthty 8 (June 1976), 244 (abstract only)

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Design, Measurement, Performance, Theory