Change search
ReferencesLink to record
Permanent link

Direct link
Provable per-link delay-optimal CSMA for general wireless network topology
Show others and affiliations
2014 (English)Conference paper (Refereed)
Abstract [en]

In the past few years, an exciting progress has been made on CSMA (Carrier Sense Multiple Access) algorithms that achieve throughput and utility optimality for wireless networks. However, most of these algorithms are known to exhibit poor delay performance making them impractical for implementation. Recently, several papers have addressed the delay issue of CSMA and yet, most of them are limited, in the sense that they focus merely on specific network scenarios with certain conditions rather than general network topology, achieve low delay at the cost of throughput reduction, or lack rigorous provable guarantees. In this paper, we focus on the recent idea of exploiting multiple channels (actually or virtually) for delay reduction in CSMA, and prove that it is per-link delay orderoptimal, i.e., O(1)-asymptotic-delay per link, if the number of virtual channels is logarithmic with respect to mixing time of the underlying CSMA Markov chain. The logarithmic number is typically small, i.e., at most linear with respect to the network size. In other words, our contribution provides not only a provable framework for the multiple-channel based CSMA, but also the required explicit number of virtual-multi-channels, which is of great importance for actual implementation. The key step of our analytic framework lies in using quadratic Lyapunov functions in conjunction with (recursively applying) Lindley equation and Azuma's inequality for obtaining an exponential decaying property in certain queueing dynamics. We believe that our technique is of broad interest in analyzing the delay performances of other general queueing systems.

Place, publisher, year, edition, pages
2014. 2535-2543 p.
, Proceedings - IEEE INFOCOM, ISSN 0743166X
Keyword [en]
Algorithms, Carrier communication, Electric network topology, Markov processes, Wireless networks, Delay performance, Delay reduction, General networks, Multiple channels, Multiple-channel, Network scenario, Quadratic lyapunov function, Virtual channels, Carrier sense multiple access
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-167624DOI: 10.1109/INFOCOM.2014.6848200ISI: 000361544200283ScopusID: 2-s2.0-84904438161ISBN: 9781479933600OAI: diva2:813886
33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, 27 April 2014 through 2 May 2014, Toronto, ON

QC 20150525

Available from: 2015-05-25 Created: 2015-05-22 Last updated: 2015-10-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Yun, Seyoung
By organisation
Automatic Control
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link