Generalized diffusion limit for queue-length processes

Let Un,k(t)U_{n,k}(t) denote the scaled fraction of queues with at least kk customers, let Fn,k(0)F_{n,k}(0) denote the corresponding initial tail fractions, and let uk(t)u_k(t) be the fluid-limit functions. Fix kKk\le K, where KK is defined in the paper, and suppose that d(n)d(n) is the buffer-size parameter. Assume

limnnd(n)=.\lim_{n\to\infty}\frac{n}{d(n)}=\infty.

Assume that Un,k(0)U_{n,k}(0) is deterministic for all nn and kKk\le K, and that there exist v1,,vKR+v_1,\dots,v_K\in\mathbb{R}_+ and v1,,vKRv_1^*,\dots,v_K^*\in\mathbb{R} such that

limnnd(n)k(Un,k(0)vk)=vk.\lim_{n\to\infty}\sqrt{\frac{n}{d(n)^k}}\left(U_{n,k}(0)-v_k\right)=v_k^*.

Additionally, assume

limnnd(n)K+1(Fn,K+1(0)+Fn,K+2(0)+)=0.\lim_{n\to\infty}\sqrt{n\,d(n)^{K+1}}\left(F_{n,K+1}(0)+F_{n,K+2}(0)+\cdots\right)=0.

Generalized diffusion-limit conjecture. As nn\to\infty,

nd(n)k(Un,k(t)uk(t)+1d(n)uk+1(t))Zk(t),\sqrt{\frac{n}{d(n)^k}}\left(U_{n,k}(t)-u_k(t)+\frac{1}{d(n)}u_{k+1}(t)\right)\Rightarrow Z_k(t),

where uK+1(t)u_{K+1}(t) is interpreted as zero. The process Z1(t)Z_1(t) is the solution of

Z1(t)=v1+λB1(1)(t)0t1eu1(s)dB1(2)(s)0teu1(s)Z1(s)ds,Z_1(t)=v_1^*+\sqrt{\lambda}\,B^{(1)}_1(t)-\int_0^t\sqrt{1-e^{-u_1(s)}}\,\mathrm{d}B^{(2)}_1(s)-\int_0^t e^{-u_1(s)}Z_1(s)\,\mathrm{d}s,

and, for k=2,,Kk=2,\dots,K, Zk(t)Z_k(t) is the solution of

Zk(t)=vk+0tλuk1(s)dBk(1)(s)0tuk(s)dBk(2)(s)0tZk(s)ds,Z_k(t)=v_k^*+\int_0^t\sqrt{\lambda u_{k-1}(s)}\,\mathrm{d}B^{(1)}_k(s)-\int_0^t\sqrt{u_k(s)}\,\mathrm{d}B^{(2)}_k(s)-\int_0^t Z_k(s)\,\mathrm{d}s,

for independent Wiener processes Bk(1)(t)B^{(1)}_k(t) and Bk(2)(t)B^{(2)}_k(t). The conjecture concerns a proposed extension of the paper's proved diffusion limit: the different scaling orders for successive queue-length levels introduce complications for the proof, and the generalization remains unproved in the source.

Sources & referencesView supporting material

Primary source

A. B. Dieker and Tonghoon Suk, “Randomized longest-queue-first scheduling for large-scale buffered systems”, arXiv:1306.5347 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.