Journal of the Association for Computing Machinery, Vol. 42, No. 3, May 1995, pp. 641–657.

An Optimal Service Policy for Buffer Systems

ALEXANDER BIRMAN

H. RICHARD GAIL

SIDNEY L. HANTLER

ZVI ROSBERG

AND

MOSHE SIDI

Abstract. Consider a switching component in a packet switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing port 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 which 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.

Categories and Subject Descriptors. C.2.1 [packet networks]; C.4 [performance attributes]; D.4.4 [buffering]; D.4.8 [queueing theory]

General Terms. Algorithms, Design, Performance

Additional Key words and Phrases. Buffer overflow, gradual input, multiplexor, parallel queues, service discipline, switch

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.