[Tccc] Jackson Network and Queueing Theory
Prof. Victor Li
vli
Fri Nov 25 06:22:56 EST 2011
Dear Flaminio and Luca,
Our explanation is as follows.
Theorem 1 given in [3] actually concerns the
asymptotic behavior of the random variables
M_n with n < 0. Such random variables are not the
physical waiting times W_n. For a G/GI/1 queue,
the random sequence M_n with n < 0 behaves
in the same way as the random sequence W'_n with n > 0,
see (4). Both M_n and W'_n are monotonic in n
but W_n is not. By replacing the index
-k of U_{-k} in \sum U_{-k} (see the
condition given in [3]) with j, one obtains
the sum D_n in (6).
The claim that the condition given
in [3] is sufficient for a queue to be stable implies an
assumption that (6) is the only cause of the instability.
The fact that such an assumption is incorrect has
been ignored in the literature. Actually, (5) is a
consequence of (6). If the condition given in [3]
does not hold, then (6) holds, which implies (5).
On the other hand, when the condition given in [3]
holds, (6) does not hold, but (5) can still hold
if the service times are unbounded. There are different
cases in which (5) holds. Violating the condition
given in [3] is only one of such cases, and in this case the
queue is considered unstable in [3] and [2]. This shows that
(5) is actually used in [3] and [2] to characterize the
instability of the queue. This is the origin of (5).
In contrast to the condition
given in [3], which is based on an incorrect assumption
that (6) is the only cause of the instability, (5) covers
all the cases in which a queue is unstable. This is
why they differ. Since the condition given in [3]
is only necessary but not sufficient to prevent
a queue from being unstable as characterized by (5),
a queue with unbounded service times can still be unstable.
We have responded to both of your objections (a) and (b).
In summary, (5) is the criterion of
the instability actually used in [3] and [2].
But after the physical waiting times W_n are replaced
by M_n or W'_n, the instability criterion (5) is ignored.
The condition given in [3] is only necessary but not
sufficient for a queue to be stable.
Best regards,
Guang-Liang and Victor
-----Original Message-----
From: Flaminio Borgonovo
Sent: Wednesday, November 23, 2011 7:31 PM
To: Prof. Victor Li
Cc: barletta at elet.polimi.it ; tccc at lists.cs.columbia.edu
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Dear Victor and Guang-Liang,
following our messages on your paper, I, and the collegue that signs
below, have discussed it thouroughly, and we have agreed that,
besides logical issues in Theorem 1, there are other primary
objections to your proof, originated by (5).
a) Theorem 1 derives from relation (5), that we have interpreted as
(roughly speaking):
- if waiting times are unbounded the queue is unstable
Since a variable can be unbounded even if finite, as it is for the
negative exponential, (5) implies that queues with waiting times with
such distributions cannot be stable. In our view, the thesis of
Theorem 1 is already here: unbounded W_n implies unstable queue.
Therefore (contrapositive) stable queue implies bounded W_n. Therefore
we must clarify the origin of (5).
b) We have looked at Loynes'article, that you cite as [3], and we have
not found assertion (5), that you refer to [3]. The only result that
resembles (5) is, in Loynes' article, Theorem 1, which asserts that "a
queue is stable iff
lim_n sup sum U_k < infty",
which is completely different from your (5). The condition above, in
fact, is not contradicted by negative exponential service and
interarrival times with E[U_k]<0. In this case, in fact, E[sum
U_k]=-infty.
Can you explain these objections?
Regards
Flaminio and Luca Barletta
Prof. Flaminio Borgonovo
Dip. di Elettronica e Informazione
Politecnico di Milano
P.zza L. Da Vinci 32
20133 Milano, Italy
tel. 39-02-2399-3637
fax. 39-02-2399-3413
e-mail: borgonov at elet.polimi.it
URL [1]http://home.dei.polimi.it/borgonov/index.html
visit [2]http://www.como.polimi.it/Patria/
References
1. http://home.dei.polimi.it/borgonov/index.html
2. http://www.como.polimi.it/Patria/
_______________________________________________
IEEE Communications Society Tech. Committee on Computer Communications
(TCCC) - for discussions on computer networking and communication.
Tccc at lists.cs.columbia.edu
https://lists.cs.columbia.edu/cucslists/listinfo/tccc
More information about the TCCC
mailing list