[Tccc] Jackson Network and Queueing Theory

Flaminio Borgonovo borgonov
Wed Nov 16 09:11:43 EST 2011


   Dear Victor and Guang-Lian,
   after refreshing some logical definitions,
   the issue has become, to me, simpler than I thought:
   in your notation the first statement of the theorem writes
    1.     V(X,Y)=FALSE
   This does not mean a logical implication. To demonstrate
    a logical implication you should also demonstrate the entire table of
   thruth:
    2     V(X,Y')=TRUE
   3     V(X',Y')=TRUE
   4     V(X',Y)=TRUE
   Although I'm convinced that  2 holds , 2 is not automatically implied
   by 1.
   On the contrary 3 is not likely to hold.
   Furthermore, 4 is the very statement you want to prove.
   Then, you can not assume logical implication. By assuming it,
   you assume what you want to prove.
   This, I think, is what Lachlan implied in his first messages.
   Similarly,
    6.     V(Y',X')=FALSE
   does not  mean
   7     V(Y',X)=TRUE
   regards,
   Flaminio
   At 15.12 15/11/2011, Prof. Victor Li wrote:

     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: [1]Flaminio Borgonovo
     Sent: Tuesday, November 15, 2011 2:01 AM
     To: [2]Prof. Victor Li ; [3]Flaminio Borgonovo ;
     [4]lachlan.andrew at gmail.com
     Cc: [5]tccc at lists.cs.columbia.edu ; [6]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] [7]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. [8]http://home.dei.polimi.it/borgonov/index.html
       2.
     [9]http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_
     Revisited.pdf
       3. [10]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
     [11]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 [12]http://home.dei.polimi.it/borgonov/index.html
     visit  [13]http://www.como.polimi.it/Patria/

   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 [14]http://home.dei.polimi.it/borgonov/index.html
   visit  [15]http://www.como.polimi.it/Patria/
   

References

   1. mailto:borgonov at elet.polimi.it
   2. mailto:vli at eee.hku.hk
   3. mailto:borgonov at elet.polimi.it
   4. mailto:lachlan.andrew at gmail.com
   5. mailto:tccc at lists.cs.columbia.edu
   6. mailto:glli at eee.hku.hk
   7. http://home.dei.polimi.it/borgonov/index.html
   8. http://home.dei.polimi.it/borgonov/index.html
   9. http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_Revisited.pdf
  10. https://lists.cs.columbia.edu/cucslists/listinfo/tccc
  11. https://lists.cs.columbia.edu/cucslists/listinfo/tccc
  12. http://home.dei.polimi.it/borgonov/index.html
  13. http://www.como.polimi.it/Patria/
  14. http://home.dei.polimi.it/borgonov/index.html
  15. http://www.como.polimi.it/Patria/



More information about the TCCC mailing list