An optimal service policy for buffer systems.
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.
Introduction
We consider a system consisting of several input channels and a single output channel.
Variable length messages, with a maximumlength of L bits, arrive over each input channel
and are stored in the buffer associated with that channel. The buffers are emptied into the
output channel by a single server whose speed is at least as great as the aggregate speed
of the input channels. The system is to be work-conserving subject to the constraint that
service can only be provided to complete messages. Accordingly, the server:
(a) may not begin serving a buffer until it contains at least one complete message;
(b) cannot be idle if at least one buffer contains a complete message;
(c) serves complete messages without interruption.
Service is provided by the server according to a rule which, given the contents of each
buffer at the beginning of a service period, determines the buffer to be served next. Simple
examples of such a service policy include Exhaustive Round Robin and First Come First
Served.
The system described above can be found in various devices, e.g., packet switches
in communication networks. Here the server is the switch itself, and the service policy
provides the rule that determines which buffer the switch will serve. In such systems it
is important, for economic reasons, to minimize the amount of storage required in each
buffer [11]. Yet the buffers must be large enough to limit overflow (the loss of messages
which arrive to a full buffer). Ideally, the buffers would be designed to eliminate overflow.
Our interest is in a nonoverflowing policy that minimizes the size of the largest buffer
required under any message arrival pattern. In many applications, it is also desirable that
the buffer storage required for each channel be independent of the number of channels
and their relative speeds. This will enable the reuse of the input channels when the
system is reconfigured to allow higher speed channels or a larger number of channels.
This design problem was studied in [3] where the Exhaustive Round Robin (ERR)
service policy was analyzed. Under this policy the buffers are served in cyclic order, and
once the service of a buffer starts it continues until all complete messages in that buffer
are exhausted. It was shown there that when the speeds of the input channels are equal, a
buffer at every input channel of capacity 3:35L is sufficient to prevent overflow. However,
when the speeds are not equal, the required buffer sizes depend on the relative speeds
and grow linearly with the number of input channels. Recently in [13], the upper bound
for equal speed channels and ERR was improved to 3:307L, and a lower bound of 3:051L
was also provided. In the same paper Gated Round Robin (GRR) was investigated
for equal speeds, and an upper bound of 3L was found. Other policies that have been
studied include First Come First Served (FCFS) and Longest Queue First (LQF). In [2]
the FCFS policy was shown to require buffers of capacity 2L to prevent overflow in the
case of equal speed channels, but in the unequal speed case the buffer sizes exhibit the
same linear behavior in the number of channels as ERR. A similar phenomenon has been
established for LQF in [7]. The required buffer storage to guarantee no overflow is again
2L for the equal speed case, but it depends on the number and relative speeds of the
input channels in the unequal speed case and increases logarithmically in the number of
channels. Finally, we mention a recent paper [9] in which a study of a discipline called
fair queueing was presented. Translating that work into the context of the above system
model, it was shown that an upper bound of 2L guarantees no overflow in the equal speed
case under the fair queueing service policy.
In this paper we introduce and analyze a class of buffer service policies, called Least
Time to Reach Bound (LTRB), that satisfies (a)-(c), guarantees no overflow, and for
which the buffer storage required at each input channel is 2L in all cases. The storage
required under LTRB is not only independent of the number of channels and their relative
speeds, but it is also optimal in the sense that any such nonoverflowing policy requires
at least as much storage. The LTRB policy operates as follows. When the service of a
message is completed, the next message to be served is chosen from a buffer that would
overflow first if all input channels were to remain continuously busy and none were served.
The model of arrivals is the standard gradual input or noninstantaneous input model
often used to study switches and communication networks. This model has appeared
extensively in the literature in the analysis of these systems [1, 5, 6, 10, 12] and has also
been used in the analysis of dams [4, 8]. The noninstantaneous input model describes
more accurately than instantaneous input models real systems for which the interarrival
times between messages are limited by the speeds of the input channels. An input channel
may be either "on" (bits are arriving) or "off" (no bits are arriving). Messages are loaded
gradually into the buffer as they arrive, as opposed to arriving instantaneously. We
emphasize that the results proved here hold for every instance of systems satisfying the
assumptions, regardless of the distribution of arrivals, service times and on/off statistics
of the input channels.
The remainder of the paper is organized as follows. In Section 2 the noninstantaneous
input model is described and the LTRB class of service policies is presented. In Section
3 a proposition involving the properties of a certain set of difference equations is proved.
In Section 4 this proposition is used to establish that LTRB does not overflow with a
buffer storage of only twice the maximum message length. In Section 5 a brief discussion
of the results is presented.
Consider a system with N input channels, each with an input buffer. Let S i ? 0,
, be the rate (in bits/sec) of channel i. As discussed in the introduction,
we assume the gradual input or noninstantaneous input model of arrivals. Bits arriving
through channel i are stored in its corresponding input buffer, and if that buffer is full
the bits are lost. An input channel may be either in an on state, during which S i bits/sec
are arriving, or in an off state, during which no bits are arriving at that channel. The
arriving bits form messages. Each message consists of not more than L bits. We do not
impose any statistical assumptions about the on and off periods of the input channels or
on the message lengths.
A single server, whose service rate is S (bits/sec), serves the messages residing at the
input buffers. Without loss of generality we normalize the server speed to 1. The
rate S i then represents the speed of channel i relative to the service rate. The aggregate
rate of the input channels is at most the service rate, that is,
1. The server
is restricted to serve only complete messages. Thus, if a buffer contains only part of a
message, that message cannot be served until the complete message is present in the
buffer. In addition, messages are served without interruption, so that message fragments
cannot be served. Finally, the server is work-conserving, i.e., it is not idle if there is a
complete message at some buffer.
Since only complete messages are served, the epochs at which the server decides upon
the next message to handle are times when at least one buffer contains a complete mes-
sage. Since messages are served without interruption and the server is work-conserving,
these decision epochs are either instants of service completion or, if the server is idle,
instants when at least one complete message is formed at some buffer.
We assume that when the system starts to operate no buffer contains more than L
bits, so that the total number of bits in the system initially is not greater than NL bits.
Since the service rate is at least as large as the aggregate arrival rate when the server is
busy, and since no buffer can contain L or more bits when the server is idle, the total
number of bits in the system cannot exceed NL bits at any time.
To define the class of LTRB policies we need the following notation. Let Q
be the number of buffered bits at channel i at time t. As noted
above, the Q i (t) satisfy
t. Define the quantity ' i (t) as
We note that if Q i (t) - 2L, then ' i (t) is simply the time it will take for the queue size at
channel i to reach a buffer size of 2L, assuming a continuous stream of bits arrive over
the channel. Policies from the LTRB class operate by attempting to serve any buffer
with the minimal "time to reach bound." However, since only complete messages can be
served, a slight variation to this scheme is necessary.
The Least Time to Reach Bound Class of Policies
At a decision epoch - , the server chooses to serve a buffer i, from among
those buffers with a complete message, for which ' i (- ' j (- ) for all buffers
j with at least L bits.
One member (policy A) from this class of policies is the following:
At a decision epoch - , the server chooses to serve a buffer with the minimal
those buffers with a complete message.
Another variant (policy B) from the LTRB class is the following:
At a decision epoch - , the server chooses to serve a buffer with the minimal
those buffers with at least L bits. If no buffer has L or more
bits, then any buffer with a complete message is chosen.
We now proceed to give a mathematical description of the LTRB class of policies. At
each decision epoch - , the channel chosen to be served is required to have a complete
message to transmit. Note that Q i (- L is equivalent to ' i (- L=S i . Therefore, any
channel satisfying ' i (- L=S i must have a complete message, and it is thus eligible to
be chosen for service. Define
has at least L bits at -g (2)
and
has a complete message at -g: (3)
Since L is the maximum message length, we have L(-
although we may have L(- chosen to be served, then F (-
An LTRB policy is one for which ' F (- '
Let F(- ) be the set of channels from which the service policy chooses according to
the minimal ' i (- ), i.e.,
It should now be clear that the relation
for all decision epochs - , yields the class of LTRB policies. Setting F(-
obtain the first example (policy A) that was discussed above. The choice of channel to
serve is the one with minimal time to reach bound over all channels with a complete
message. Setting F(- gives the
other extreme (policy B). The choice of channel to serve is the one among those with at
least L bits with minimal time to reach bound. If all channels have less than L bits, then
any channel with a complete message may be chosen.
Our main goal is to prove that any member of the LTRB class of policies requires
buffer storage of only 2L bits at each input channel to prevent overflow, for any number
of channels N and any set of channel speeds fS i g. That is, we will prove the following.
Theorem 1 Consider a system of N channels with channel speeds S i ,
server speed S -
operating under any member of the class of LTRB policies.
Then
In [3] it was shown that a buffer size of 2L is a lower bound for any policy satisfying
properties (a)-(c) of Section 1. Thus we obtain the following result immediately from
Theorem 1.
Theorem 2 The LTRB class is optimal in terms of buffer storage for policies that are
work-conserving and for which only complete messages are served.
3 Analysis
3.1 Preliminaries
To determine whether or not overflow occurs under a given policy, only the buffer sizes at
decision epochs need to be examined. The reason is that overflow occurs if and only if it
occurs at a decision epoch (necessarily during a busy period). This can be seen as follows.
Consider an arbitrary busy period, and let - n , beginning of
the nth service. Note that these instants of time constitute the decision epochs within
that busy period. We claim that it is enough to show that overflow does not occur at
these decision epochs. For suppose that overflow occurs at some time t that is not a
decision epoch, and let channel i be the one that overflows. We have
some n, since channel i will still have at least one complete message at the end of the
present service. If channel i has already overflowed at the decision epoch - n , then the
claim holds. If channel i has not overflowed at - n , then clearly it is not being served at t,
for otherwise its queue size would not increase between - n and t. Therefore, at the next
decision epoch - n+1 (the end of the current service), overflow will still occur at channel
i. In fact, Q being served at time t, while Q
if channel i is not being served at time t. Thus overflow occurs during a busy period
if and only if it occurs at a decision epoch within that busy period, and we need only
concentrate on these points in time.
Note that the queue size at each channel at the start of the busy period is at most L.
That is, the initial value Let oe(n) be the length of the
nth message to be served during the busy period. Then it also represents the nth service
time, since the server speed is normalized to 1. Let , be the time during
this service when channel i actually receives input (thus
F (n) be the channel that is chosen to be served at the nth decision epoch. Then, when
service is completed the value of ' i for any channel i 6= F (n) that has not been served will
decrease by ffi i (n), while that for channel F (n) will increase by (oe(n)=S F (n)
That is, at the completion of service we have '
(n). Note that these equations hold for any
service policy F under our modeling assumptions. We will study difference equations of
this type under a general framework that includes equations obtained when F belongs
to the class of LTRB policies.
3.2 Generalized Framework
The above discussion suggests the study of the following mathematical model in a general
setting. We are given L - 0 and
A state is an N-vector We are also given an initial state ' satisfying
Our interest is in certain sequences
which are called triples and are defined as follows: T
T determines a state trajectory \Theta = ('(0);
satisfies
As mentioned above, the evolution of the states of the channels within a busy period as
defined by (1) follows (7) for an arbitrary service policy F . However, there are additional
constraints on the equations generated from the behavior of the queueing system that
models the switch. As an example, messages of length L cannot be consecutively chosen
for service from the same channel at the beginning of a busy period, since sufficient
time would not have elapsed for the second message to arrive. As another example, the
amount of bits in any buffer cannot become negative (the value of ' i cannot become larger
than 2L). We will prove a proposition on difference equations of type (7) without taking
into account such constraints. All equations that model the behavior of the queueing
system described above will be included, but they will constitute a small set of the cases
covered by our result. Although the proposition is quite general from a mathematical
point of view, the significance of the framework developed above is that it allows certain
inductive arguments to be carried through which yield the queue size upper bound of
Theorem 1. Otherwise, such additional constraints would always have to be taken into
account, complicating the arguments.
We next describe the triples that we wish to consider. Let T be a triple with corresponding
state trajectory \Theta, and define
A triple T is admissible at step n if ' F (n) (n) - ' i (n) for all i 2 L T (n). T is admissible if
it is admissible at In terms of the queueing model, note that policies from
the LTRB class yield triples that are admissible.
One example of an admissible triple is obtained if the index F (n) corresponds to the
minimal value of ' i (n) at each step n. A triple T is strict at step n if ' F (n) (n) - ' i (n)
. T is strict if it is strict at In the queueing model, if at
each decision epoch the channel with the minimal ' i as defined in (1) has a complete
message, choosing these channels to serve yields a strict triple. Furthermore, the choices
F (n) constitute a policy that is necessarily a member of the LTRB class.
To prove Theorem 1 we will show that the trajectory \Theta is always positive, namely,
We carry out the proof in three steps. First,
we show that if T is a strict triple, then ' i (n) - L for
then handle admissible triples T which have nonstrict steps and show that \Theta is positive
This case corresponds in the queueing model
to all channels remaining on for the same percentage of time during each service. Finally,
we prove that \Theta is always positive for any admissible T . Note that this last result yields
Theorem 1, since for ' i as defined in (1), ' i positive at the decision epochs of a busy
period implies that no overflow occurs at channel i given a buffer of size 2L.
Before continuing, we introduce some notation. For a set J '
two N-vectors
i2J a i b i . We also use
the notation
. When simply write a \Delta b.
3.3 Strict Triples
We now prove the following proposition about strict triples.
Proposition 1 Let T be a triple with corresponding state trajectory \Theta. If T is strict,
then
Proof: We will first prove by induction on n that (S \Delta '(n)) J
By hypothesis, (S \Delta '(0)) J
so that the claim holds for
Now assume it holds for
by the induction hypothesis and the fact that (S \Delta ffi(m)) J
- oe(m). If F (m) 62 J , then
We claim that (S \Delta '(m)) J
which will complete the proof. Suppose not,
so that
Since T is strict (at step m in particular), then ' F (m) (m) - ' i (m) for
Multiplying the ith equation by S i and summing over i 2 J , we obtain the inequality
. Thus, from (10), it follows that
S fF (m)g, we have from (10) and (11)
which contradicts the induction hypothesis. This completes the proof of the claim.
Specializing to the case shows that ' i (n) - L for
which proves the proposition. 2
It is interesting to note that, for certain queueing models, the channel with the minimal
defined in (1) is guaranteed to have a complete message, and thus a strict
policy can always be implemented. For example, consider the case when S
continuously on, and all buffers initially contain L
bits. For equal speed channels, the channel with the smallest value of ' i has the largest
queue size, as is apparent from (1). Further, since all channels initially start with L bits,
there are no off periods, the total number of bits in the system always
remains at NL. Thus, the maximal queue size is at least L bits at any time, and so the
channel with the smallest ' i has a complete message.
3.4 Uniform Triples
We can now prove the main result for uniform triples, i.e., admissible triples satisfying
the additional assumption that ffi i . For the queueing
model, this case corresponds to all channels remaining on for the same percentage of time
while messages are being served. One example of this behavior occurs when
which is the case of continuous input at all channels during the service time
of the nth message. The other extreme, when corresponds to
the case of no input at any of the channels.
When shows that the positions of '
compared to those of ' i (n) do not change, except for index F (n). That is, we have
(n). This property is used
extensively in the proof of the following proposition.
Proposition 2 Let T be a triple with corresponding state trajectory \Theta. Assume that
If T is admissible, then
Proof: Consider any step n ? 0. If T is not strict at n, then the theorem clearly holds,
since the minimal ' i must satisfy ' i (n) ? L=S i by (8). Thus we may restrict attention
to uniform triples that are strict at n. Such triples may be classified by the number
nonstrict steps in 1g. We will prove the theorem by induction
on K. The case which corresponds to triples that are strict at the first n steps,
holds by Proposition 1. Assume the theorem is true for all uniform triples with
nonstrict steps, and we will show it is true for is a uniform triple
nonstrict steps in be the last nonstrict step before n,
so that T is strict at steps m+
Note that R 6= ; by assumption. Since T is an admissible triple, we have R ' N nL T (m),
that is,
The index F (m+1) must correspond to the minimal ' i at step m, since T is not strict
at m but is strict at m+ 1, and
and we have
Thus the theorem holds if may assume that m+ 1
The proof of the induction step splits into two cases, depending on whether or not
only members of R are chosen between steps m+ 1 and n.
Case 1: First, suppose that
We claim that (15) implies (12). It is sufficient to prove that ' F (n) (n) ? 0, because T is
strict at n. Set K (n)g. Since K includes all of the indices chosen
during steps m+
Since K ' R and (S \Delta ffi(m)) K
- L, we have using (14)
Note that this proves the claim if F (m
If jKj - 2, there is 1g be the last step prior
to n such that (l). This implies
p=l
Since T is strict at l, ' F (l) (l) - ' F (n) (l), so that
p=l
where we have used the fact that ffi F (l) 1. Therefore, since
L, we have shown that
Summing equation (17) over such i, we obtain
From equations (16), (18) and SK ? 0, we find that ' F (n) (n) ? 0. This completes the
proof of the induction step when (15) holds.
Case 2: We now suppose that
1 be the first step in fm ng such that F (k   We claim that
This obviously holds so we may assume that F (k
not chosen between steps m and k   , we have
p=m
Similarly, F (m) was only chosen at step m, and so
p=m
Using inequalities yield
However, holds.
1 be the first step in fm+ ng satisfying (20). Note that for i 2 R 6= ;,
since As T is strict at m+ 1, this implies
and so ng. We wish to "delay" choosing F (m) until step k to obtain
a triple with only - nonstrict steps.
Consider the triple defined by
and let be the corresponding state trajectory.
we have
which follows from (21).
We want to show that U is strict at steps and that '(n). Then the
induction hypothesis will yield the proposition. For l
that . Therefore, for i 6= F (m),
since T is strict at l + 1. Also, for F (m),
Thus U is strict for l 2 1g. At step k, we have
from (20). Thus, for i 6= F (m),
since T is strict at k + 1. This shows that U is also strict at k.
We now claim that OE(k 1). To see this, note that for i 6= F (m) we have
and for F (m) we have
Thus As a consequence of this result, the triple U is
strict for since U and T (strict) agree there. Thus U has - nonstrict steps
in by the induction hypothesis.
This completes the proof of Proposition 2. 2
Relating the above proof to the queueing model, in case 1 only channels with less
than L bits at the mth decision epoch are chosen for service between m+1 and n. These
channels, which correspond to the minimal ' i for epochs
size at m, and a direct calculation shows that no overflow occurs by only serving them.
In case 2, a policy with less nonstrict choices is constructed by delaying the service of
the channel chosen originally at epoch m until later in the busy period.
3.5 Admissible Triples
We now extend the above result to admissible triples with arbitrary ffi(n). For a triple
define the set
Further, define I to be the cardinality of I(T ).
We can now prove the main proposition on admissible triples.
Proposition 3 Let T be a triple with corresponding state trajectory \Theta. If T is admissible,
then
Proof: It is clear that, for each n, there is an admissible triple U n that agrees with T
for 1. Thus we need only prove the proposition
for admissible triples T with I(T 1. The proof is by induction on I(T ).
When I(T Therefore,
the result holds in this case by Proposition 2. Now assume the proposition holds for
admissible triples with I = -, and we show it holds when I = -+ 1. Let T be admissible
with choose step n and j 2 N such that
The proof of the proposition splits into two cases, depending on whether or not the
index j is ever chosen after step n. In each case we will identify an admissible triple U
related to T with then use the induction hypothesis.
Case 1: First, suppose that
In this case ' j (l) ? ' F (l) (l), so that j 6= F (l) for That is, the index
j is not chosen after step n. Define the triple U as follows:
Note that be the state trajectory corresponding to
U . Clearly
for such l, we have using (24)
It now follows that U is admissible, because T is. Also, ' i (l) - OE i (l) for
by the induction hypothesis.
Case 2: Next suppose that
for some l 2 fn k be the first such step (k ? n). Define the triple
It is easy to verify that U is a triple. For example,
shows that 0 -(k) - L. Further, we have be the
state trajectory corresponding to U .
k, the state OE(l) is given by (26).
For l 2 fn (see the derivation of equation (27)),
so that U is admissible at l. Next, by definition of k,
Thus U is admissible at k since T is.
We now consider step k + 1. For i 6= j we have
while for j we have
This implies that so U is admissible for such
l. Therefore, U is an admissible triple such that
the induction hypothesis. This completes the proof of Proposition 3. 2
To describe the above proof in terms of the queueing model, recall that the case when
all channels remain on for the same percentage of time while messages are being served
is covered by Proposition 2. To handle the general case, channel j is turned on for an
additional length of time during the nth service, so that the on periods
of the channels are more uniform. That is, are
added to the buffer at channel j. Case 1 corresponds to channel j never being chosen for
service (for example, it may never contain a complete message). Case 2 corresponds to
serving the dummy bits while keeping all channels turned off during their service.
4 Optimality of LTRB
We now use the results of Section 3 to prove the optimality of the least time to reach
bound (LTRB) class of service policies introduced in Section 2. Our interest is in a
service policy for which the buffer size required at each channel to prevent overflow is
independent of the number of channels and their speeds. We will show that not only do
the LTRB policies possess such a property, but in addition the members of this class are
optimal in terms of buffer size. Our approach is to examine any instance of the evolution
of the behavior of the system and apply Proposition 3 of the previous section to conclude
that no overflow will occur. The proof will yield an upper bound of 2L for the buffer
size at each channel to prevent overflow. However, as mentioned in Section 2, the value
2L is a lower bound for any policy that is work-conserving and for which only complete
messages are served. Thus the proof of the upper bound shows that LTRB is optimal
among all such policies.
Recall that L is the maximum message length, and S i , are the relative
speeds of the N channels. The number of bits in storage at channel i at time t is denoted
is the time for the queue size at
channel i to reach 2L, assuming a continuous flow of bits at rate S i and no service given
to channel i. Since overflow occurs if and only if it occurs at a decision epoch during a
busy period, we may concentrate on these instants of time. Now recall that the states ' i
at decision epochs during a busy period satisfy difference equations of the form (7). Here
oe(n) is the length of the message chosen for service at the nth epoch, F (n) is the channel
containing that message, and , is the length of the corresponding on
period for channel i. Further, the queue size at channel i at the beginning of a busy
period is at most L, so that the initial state ' satisfies
these definitions, the sequence (oe(n); ffi(n); F (n)), represents a triple as
defined in Section 3. It is also clear that members of the LTRB class yield triples that
are admissible, and so the results of the previous section may be applied to these policies.
As mentioned before, certain restrictions on the triples arise naturally in the queueing
model. For example, the buffer size Q i (n) cannot be negative (the value of ' i (n) cannot go
above 2L), while this is allowed in the triples studied in Section 3. Also, in the queueing
model a message cannot be transmitted until sufficient time has elapsed for it to arrive
(for example, it may not be possible for a channel to transmit L bits in two successive
steps). Thus the set of triples generated by the queueing model is a small subset of the
set of all possible triples considered in Section 3. However, we may apply the general
result obtained in that section to show that no overflow can occur for a system operating
under an LTRB policy which has buffers of size 2L.
Theorem 1 Consider a system of N channels with channel speeds S i ,
server speed S -
operating under any member of the class of LTRB policies.
Then
Proof: As discussed above, only decision epochs - n ,
busy period need to be considered. When all channels remain on for the same percentage
of time during the service of each message, then
which is the situation covered by Proposition 2. The more general case when input flow
to the channels can be turned on and off arbitrarily is handled in Proposition 3. 2
Theorem 1 shows that the bound of 2L is valid for any number of channels and
any set of channel speeds. However, in certain cases an even smaller bound may hold.
For example, suppose all channel speeds are identical (S
In this case,
is a constant independent of the channel. Thus choosing
the minimal ' i is equivalent to choosing the buffer with the maximal queue size among
all channels with a complete message, which shows that the Longest Queue First policy
(LQF) is in the LTRB class. Using results from [7] for LQF, the upper bound on buffer
storage for this case is, in fact,
We have shown that the policies from the LTRB class require buffer storage of 2L,
which is independent of the number of channels and their relative speeds. These policies
are also optimal in terms of storage. To see this, first note that in [3] an example was
given to show that a buffer size of 2L is a lower bound for any policy that satisfies the
properties (a)-(c) discussed in Section 1. Let us briefly review the lower bound example.
Consider an N buffer system with channel speeds that are identical and such that their
aggregate speed is equal to the server speed (S Suppose that initially
all N buffers contain a maximal length message of L bits. After serving all but one
of the buffers at least once in an order dictated by the policy (this takes time at least
of the maximal length messages must have been served and the
server speed is unity), the final buffer that has not yet been served will contain at least
bits. As N !1 we obtain the lower bound of 2L for
any such policy.
Thus the following is an immediate consequence of Theorem 1.
Theorem 2 The LTRB class is optimal in terms of buffer storage for policies that are
work-conserving and for which only complete messages are served.
In this paper we introduced a new class of service policies, called Least Time to Reach
Bound (LTRB), for servicing messages that reside in the input buffers of a switch. According
to this policy, once a message has completed service, the next message to be
chosen is taken from a buffer that would overflow first assuming a continuous flow of bits
to all input channels and no further service. We proved that operating under this class
of policies guarantees no overflow (and thus no message loss) when the buffer storage
at each input channel is only twice the maximal length of a message for any number of
channels and any set of speeds. This class is optimal in the sense that any nonoverflowing
policy (satisfying conditions (a)-(c)) requires at least as much storage as LTRB.
There are obvious advantages of storage requirements that do not increase with
the number of incoming channels when compared to the logarithmic growth under the
Longest Queue First (LQF) service policy or the linear growth under the Exhaustive
Round Robin (ERR) and First Come First Served (FCFS) service policies. The buffer
sizes are much smaller and need not be changed every time an input channel is added to
the switch, and thus the system is more robust. Yet, to gain these advantages, the switch
must be able to determine the number of bits in each of the incoming buffers at the end
of service of each message and must also know the speeds of the incoming channels. With
ERR the switch is simpler, since the queue lengths of other buffers need not be observed
while some buffer is served. The switch with LQF is similar to that with LTRB, except
that there is no need to know the speeds of the incoming channels. In conclusion, we
observe a tradeoff between the amount of storage required and the complexity of the
switch.



--R

Stochastic Theory of a Data-Handling System with Multiple Sources
Buffer Sizing in an ISDN Frame Relay Switch.
Real Time Packet Switching: A Performance Analysis.
The Single Server Queue
Superimposed Renewal Processes and Storage with Gradual Input.
A Calculus for Network Delay
Buffer Size Requirements under Longest Queue First.
Limiting Distributions for Some Storage Problems.
How Fair is Fair Queueing?
The Stochastic Behavior of a Buffer with Non-Identical Input Lines
Communication with Few Buffers: Analysis and Design.
The Output of a Buffered Data Communication System.
Input Buffer Requirements for Round Robin Polling Systems.
--TR
How fair is fair queuing
Buffer size requirements under longest queue first

--CTR
Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Zvi Rosberg, Cell multiplexing in ATM networks, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.112-122, Feb. 1996
Amotz Bar-Noy , Ari Freund , Shimon Landa , Joseph (Seffi) Naor, Competitive on-line switching policies, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.525-534, January 06-08, 2002, San Francisco, California
Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Yossi Azar , Yossi Richter, An improved algorithm for CIOQ switches, ACM Transactions on Algorithms (TALG), v.2 n.2, p.282-295, April 2006
multiplexor;parallel queues;service discipline;gradual input;switch;buffer overflow