Mixing properties of CSMA networks on partite graphs

Alessandro Zocca*, Sem C. Borst, Johan S H Van Leeuwaarden

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider a stylized stochastic model for a wireless CSMA network. Experimental results in prior studies indicate that the model provides remarkably accurate throughput estimates for IEEE 802.11 systems. In particular, the model offers an explanation for the severe spatial unfairness in throughputs observed in such networks with asymmetric interference conditions. Even in symmetric scenarios, however, it may take a long time for the activity process to move between dominant states, giving rise to potential starvation issues. In order to gain insight in the transient throughput characteristics and associated starvation effects, we examine in the present paper the behavior of the transition time between dominant activity states. We focus on partite interference graphs, and establish how the magnitude of the transition time scales with the activation rate and the sizes of the various network components. We also prove that in several cases the scaled transition time has an asymptotically exponential distribution as the activation rate grows large, and point out interesting connections with related exponentiality results for rare events and meta-stability phenomena in statistical physics. In addition, we investigate the convergence rate to equilibrium of the activity process in terms of mixing times.

Original languageEnglish
Title of host publicationProceedings of the 2012 6th International ICST Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2012
Pages117-126
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2012
Externally publishedYes
Event2012 6th International ICST Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2012 - Cargese, France
Duration: 9 Oct 201212 Oct 2012

Publication series

NameProceedings of the 2012 6th International ICST Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2012

Conference

Conference2012 6th International ICST Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2012
CountryFrance
CityCargese
Period9/10/1212/10/12

Keywords

  • markov chains
  • hitting time
  • wireless networks
  • graph theory
  • mixing time
  • throughput
  • random access protocol
  • graph coloring

Fingerprint

Dive into the research topics of 'Mixing properties of CSMA networks on partite graphs'. Together they form a unique fingerprint.

Cite this