%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "birmanghrs95.ltx",
%%%     date      = "20 November 1995",
%%%     time      = "21:41:35 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "57602 108 470 3820",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 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.
%%%                  
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{BirmanGHRS95}

\title{An Optimal Service Policy for Buffer Systems}

\author{Alexander Birman \and H.~Richard Gail \and Sidney~L. Hantler \and Zvi
  Rosberg \and Moshe Sidi}

\Pages{641--657}

\Month{May}

\Year{1995}

\Volume{42}

\Number{3}

\maketitle

\begin{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 \emph{optimal} in the sense that any nonoverflowing policy
  requires at least as much storage as LTRB.

\end{abstract}

\begin{categories}

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

\end{categories}

\begin{terms}

Algorithms, Design, Performance

\end{terms}

\begin{keywords}

Buffer overflow, gradual input, multiplexor, parallel queues, service
  discipline, switch

\end{keywords}

\end{document}
