Balancing Reduces Asymptotic Variance of Outputs Yoni Nazarathy* EURANDOM, Eindhoven University of Technology, The Netherlands. Based on some joint works with Ahmad Al Hanbali, Michel Mandjes, Gideon Weiss and Ward Whitt QTNA 2010, Beijing, July 26, 2010. *Supported by NWO-VIDI Grant 639.072.072 of Erjen Lefeber Overview • GI/G/1/K Queue (with K • D (t ) or K ) number of customers served during • Asymptotic variance V lim • Surprising results when V ar D ( t ) t t 1 Balancing Reduces Asymptotic Variance of Outputs [0, t ] The GI/G/1/K Queue , ca 2 , cs 2 D (t ) K overflows * Assume Q (0) 0 * Load: * Squared coefficient of variation: ca , cs 2 2 variance m ean 2 Variance of Outputs V ar D ( t ) V t o ( t ) Asymptotic Variance V ar D ( t ) V lim t t V ar D (T ) V T t Simple Examples: * Stationary stable M/M/1, D(t) is PoissonProcess( ): V a r D ( t ) t * Stationary M/M/1/1 with . 1 1 1 D(t) is RenewalProcess(Erlang(2, )): V ar D ( t ) t e 2 t 4 Notes: 1 2 c 3 m * In general, for renewal process with m , : V m 2 2 * The output process of most queueing systems is NOT renewal 8 8 V V 4 Asymptotic Variance for 1 (simple) K , 1 D (t ) V ar D ( t ) t V ca A(t ) V ar A ( t ) t Q (t) V ar Q ( t ) 2 C ov A ( t ), Q ( t ) t t 2 K , 1 After finite time, server busy forever… V cs 2 K V is approximately the same as K when 1 or 1 Intermediate Summary V GI/G/1 GI/G/1/K V ca ca 2 2 ? ? cs cs 2 2 V M/M/1 V ? M/M/1/K ? B alancing R A educes symptotic V ariance of O utputs Theorem (Al Hanbali, Mandjes, N. , Whitt 2010): For the GI/G/1 queue with 1 , under some further technical conditions: 2 2 2 V 1 (ca cs ) Theorem (N. , Weiss 2008): For the M/M/1/K queue with 1 : V 2 3 3K 2 3( K 1) 2 Conjecture (N. , 2009): For the GI/G/1/K queue with 1 , under further technical conditions : V 1 3 ( c a c s ) o K (1) 2 2 BRAVO Summary for GI/G/1/K For GI/G/1/K with 1 : 2 2 2 ca cs 1 V 1 c 2 c 2 o (1) s K 3 a Proven: • K : M/M/1/K • K : * M/M/1 * Assuming finite forth moments: *M/G/1 *GI/NWU/1 (includes GI/M/1) *Any GI/G/1 with P (B x) L( x) x 1/ 2 Numerically Conjectured: GI/G/1/K with light tails K K Numerical Illustration: M/M/1/K * * V V * V * V Numerical Illustration: M/M/1 (finite T) Some (partial) intuition for M/M/1/K 0 V K-1 M 1 A sym ptotic variance of num ber of transitions Easy to see: V 4V M K References • Yoni Nazarathy and Gideon Weiss, The asymptotic variance rate of the output process of finite capacity birth-death queues. Queueing Systems, 59(2):135-156, 2008. • Yoni Nazarathy, 2009, The variance of departure processes: Puzzling behavior and open problems. Preprint, EURANDOM Technical Report Series, 2009-045. • Ahmad Al-Hanbali, Michel Mandjes, Yoni Nazarathy and Ward Whitt. Preprint. The asymptotic variance of departures in critically loaded queues. Preprint, EURANDOM Technical Report Series, 2010-001.