We examine the impact of torpid mixing and meta-stability issues on the delay performance in wireless random-access networks. Focusing on regular meshes as prototypical scenarios, we show that the mean delays in an L×L toric grid with normalized load ρ are of the order View the MathML source. This superlinear delay scaling is to be contrasted with the usual linear growth of the order View the MathML source in conventional queueing networks. The intuitive explanation for the poor delay characteristics is that (i) high load requires a high activity factor, (ii) a high activity factor implies extremely slow transitions between dominant activity states, and (iii) slow transitions cause starvation and hence excessively long queues and delays. Our proof method combines both renewal and conductance arguments. A critical ingredient in quantifying the long transition times is the derivation of the communication height of the uniformized Markov chain associated with the activity process. We also discuss connections with Glauber dynamics, conductance, and mixing times. Our proof framework can be applied to other topologies as well, and is also relevant for the hard-core model in statistical physics and sampling from independent sets using single-site update Markov chains.
Delay performance in random-access grid networks / Zocca, A; Borst, S.C.; Van Leeuwaarden, J.S.H.; Nardi, F.R.. - In: PERFORMANCE EVALUATION. - ISSN 0166-5316. - STAMPA. - 70:(2013), pp. 900-915. [10.1016/j.peva.2013.08.019]
Delay performance in random-access grid networks
NARDI, FRANCESCA ROMANA
2013
Abstract
We examine the impact of torpid mixing and meta-stability issues on the delay performance in wireless random-access networks. Focusing on regular meshes as prototypical scenarios, we show that the mean delays in an L×L toric grid with normalized load ρ are of the order View the MathML source. This superlinear delay scaling is to be contrasted with the usual linear growth of the order View the MathML source in conventional queueing networks. The intuitive explanation for the poor delay characteristics is that (i) high load requires a high activity factor, (ii) a high activity factor implies extremely slow transitions between dominant activity states, and (iii) slow transitions cause starvation and hence excessively long queues and delays. Our proof method combines both renewal and conductance arguments. A critical ingredient in quantifying the long transition times is the derivation of the communication height of the uniformized Markov chain associated with the activity process. We also discuss connections with Glauber dynamics, conductance, and mixing times. Our proof framework can be applied to other topologies as well, and is also relevant for the hard-core model in statistical physics and sampling from independent sets using single-site update Markov chains.File | Dimensione | Formato | |
---|---|---|---|
BLNZ2013.pdf
Accesso chiuso
Descrizione: Articolo principale
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
634.34 kB
Formato
Adobe PDF
|
634.34 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.