[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