[Tccc] Jackson Network and Queueing Theory
Prof. Victor Li
vli
Tue Nov 15 09:12:51 EST 2011
Dear Flaminio,
An implication is equivalent to its contrapositive.
If two implications are not equivalent, then their
contrapositives are not necessarily equivalent.
Please allow us to continue using our
notations in the following clarification.
We use X and Y to represent P(B) = 1 and
P(S) = 0, respectively. From V(T, F) = F
we have V'(T, F) = F where V' is the
contrapositive of V, and V'(T, F) = F
means "the value of V'(X' Y') is F when
(X', Y') = (T, F) with X' and Y' representing
P(S) = 1 and P(B) = 0, respectively.
Your argument concerns the contrapositive of
V(X, X'). Since V(X, X') and V(X, Y) are
not equivalent, the contrapositive of V(X, Y)
and the contrapositive of V'(X, X') are not
equivalent.
You also said that you agreed with Lachlan that V(X,Y) = F is
not applicable to all queues in the set \cal G.
This is incorrect. Please see the reply to Lachlan in the previous email.
Best regards,
Guang-Liang and Victor
From: Flaminio Borgonovo
Sent: Tuesday, November 15, 2011 2:01 AM
To: Prof. Victor Li ; Flaminio Borgonovo ; lachlan.andrew at gmail.com
Cc: tccc at lists.cs.columbia.edu ; glli at eee.hku.hk
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Dear Victor,
I'm afraid your argument below does not catch my point. Below You list
what is known as "Table of implications" and conclude that
<< If one lets the value of "P(B) = 1" be "true", then one must
let the value of "P(S) = 0" >>
I never constested the above statement (although I agree with Lachlan that it is not applicable to all queues in the set \cal G)
I only contested the use of the contrapositive argument that has led you to affirm, in theorem 1, that the following statrement is also true
<< P(S)=1 implies P(B)=1>>. I think you cannot logically derive this last statement from the former.
I restate below my argument, expliciting the attribute TRUE where I have assumed it by default
Assume:
<<P(B)=1 implies P(S)=0>> is false.
Therefore we must derive:
P(B)=1 implies P(S)=1 is TRUE
Its contrapositive statement, should be
P(S)=0 implies P(B)=0, TRUE
and not, as sustained in the paper,
P(S)=1 implies P(B)=0, FALSE , or P(S)=1 implies P(B)=1 TRUE.
best regards
Flaminio
At 05.51 14/11/2011, Prof. Victor Li wrote:
Dear Lachlan and Flaminio,
Thanks for your comments. Let V(X, Y) stand for
"X implies Y", a logical implication statement in general.
Write (X, Y) = (T, F) to mean "the value of X is T (true) and
the value of Y is F (false)". Let V(T, F) = F represent
"the value of V(X, Y) is F when (X, Y) = (T, F)".
Smilarly, V(F, F) = V(F, T) = V(T, T) = T.
In fact, V(T, F) = F and V(F, F) = V(F, T) = V(T, T) = T
correspond to the truth table values of the implication, and
V(T, F) = F is completely determined by (X, Y) = (T, F)
regardless of what X or Y means. Any other assumption
is unnecessary for V(T, F) = F.
Unless one is reasoning with a different logic,
V(T, F) = F is just fine both in general and in particular
when X and Y represent P(B) = 1 and P(S) = 0, respectively.
If one lets the value of "P(B) = 1" be "true", then one must
let the value of "P(S) = 0" be "false" because a queue with a.s.
bounded waiting time is not unstable.
Best regards,
Guang-Liang and Victor
-----Original Message----- From: Flaminio Borgonovo
Sent: Saturday, November 12, 2011 7:41 AM
To: Prof. Victor Li
Cc: tccc at lists.cs.columbia.edu ; glli at eee.hku.hk
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Hi Victor and Guang-Liang,
I think the contrapositive argument in Theorem 1 of your paper is
misused, as Lachlan suspects.
The proof of Theorem 1 shows that statement <<P(B)=1 implies P(S)=0>>
is false. Therefore we must assume:
P(B)=1 implies P(S)=1 (bounded waiting times ----> stable
queue).
Its contrapositive statement, still true, should be
P(S)=0 implies P(B)=0, (unstable queue ----> unbounded waiting times)
and not, as sustained in the paper,
P(S)=1 implies P(B)=1, (stable queue ----> bounded waiting times).
Therefore P(B)=1 for stable queues is not proved. And classic theory,
where it can be also P(S=1) and P(B)=0 (stable queue and unbounded
waiting times), is not invalidated.
This seems to invalidate Theorem 1 and the whole paper.
Regards,
Flaminio
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
On 10 November 2011 18:18, Prof. Victor Li <vli at eee.hku.hk> wrote:
> Dear colleagues,
>
> Nearly a decade ago we initiated a discussion about Jackson networks
of queues
> on this mailing list. Since then some colleagues have enquired about
our follow-up
> research regarding this issue. A recent paper by us is now available
> as a technical report at the website below:
>
>
[2]http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_Rev
isited.pdf
>
> In this paper we consider the stability of queues. We find that
> the condition given in the literature, i.e., the traffic intensity
is less
> than 1, is only necessary but not sufficient for a general
single-server queue to be
> stable. This shows again that product-form solutions of Jackson
networks
> are incorrect for such networks are actually unstable.
> In the paper we also give necessary and sufficient conditions for a
G/G/1 queue to
> be stable, and discuss the implications of our results.
>
> Queueing theory has been widely used in performance analysis of
computer and
> communication systems. Colleagues who are teaching courses on
performance
> analysis or doing research in this area, and students who are
learning how to apply
> queueing theory to performance analysis, might be interested in our
results.
> Comments on our paper are very much appreciated and can be sent to
us by
> e-mail. Thank you very much for your attention.
>
> Best regards,
>
> Guang-Liang Li and Victor O.K. Li
> _______________________________________________
> IEEE Communications Society Tech. Committee on Computer
Communications
> (TCCC) - for discussions on computer networking and communication.
> Tccc at lists.cs.columbia.edu
> [3]https://lists.cs.columbia.edu/cucslists/listinfo/tccc
>
References
1. http://home.dei.polimi.it/borgonov/index.html
2. http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_Revisited.pdf
3. https://lists.cs.columbia.edu/cucslists/listinfo/tccc
_______________________________________________
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
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 http://home.dei.polimi.it/borgonov/index.html
visit http://www.como.polimi.it/Patria/
More information about the TCCC
mailing list