On the universality of age-based scheduling in wireless networks

Bin Li, Atilla Eryilmaz, Rayadurgam Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is well-known that maximum weight scheduling, with link weights which are either functions of queue lengths or the ages of the Head-of-Line (HoL) packets in each queue, maximizes the throughput region of wireless networks with persistent flows. In particular, with only persistent flows, it does not matter for throughput optimality whether one uses queue lengths or HoL ages as weights. In this paper, we show the following interesting result: when some flows in the network are dynamic (i.e., they arrive and depart from the network and are not persistent), then HoL-age-based scheduling algorithms are throughput-optimal while it has previously been shown that queue-length-based algorithms are not. This reveals that, age-based algorithms are universal in the sense that their throughput optimality does not depend on whether the arriving traffic is persistent or not. We also present a distributed implementation of the proposed age-based algorithm using CSMA techniques, where each flow only knows its own age and carrier sensing information. Finally, we support our analytical results through simulations. The proof of throughput optimality may be interesting in its own right: it uses a novel Lyapunov function which is the sum of the ages of all the packets in the network.

Original languageEnglish (US)
Title of host publication2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1302-1310
Number of pages9
ISBN (Electronic)9781479983810
DOIs
StatePublished - Aug 21 2015
Event34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015 - Hong Kong, Hong Kong
Duration: Apr 26 2015May 1 2015

Publication series

NameProceedings - IEEE INFOCOM
Volume26
ISSN (Print)0743-166X

Other

Other34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015
CountryHong Kong
CityHong Kong
Period4/26/155/1/15

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'On the universality of age-based scheduling in wireless networks'. Together they form a unique fingerprint.

  • Cite this

    Li, B., Eryilmaz, A., & Srikant, R. (2015). On the universality of age-based scheduling in wireless networks. In 2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015 (pp. 1302-1310). [7218506] (Proceedings - IEEE INFOCOM; Vol. 26). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFOCOM.2015.7218506