Emulating round-robin for serving dynamic flows over wireless fading channels

Bin Li, Atilla Eryilmaz, R. Srikant

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

Abstract

Motivated by the Internet of Things (IoT) and Cyber-Physical Systems (CPS), we consider dynamic wireless fading networks, where each incoming flow has a random service demand and leaves the system once its service request is completed. In such networks, one of the primary goals of network algorithm design is to achieve short-term fairness that characterizes how often each flow is served, in addition to the more traditional goals such as throughput-optimality and delay-insensitivity to the flow size distribution. In wireline networks, all of these desired properties can be achieved by the round-robin scheduling algorithm. In the context of wireless networks, a natural extension of round-robin scheduling has been developed in the last few years through the use of a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time that passed since the last service time of each flow. However, the performance of this round-robin-like algorithm has been primarily studied in the context of persistent flows that continuously inject packets into the network and do not ever leave the network. The analysis of dynamic flow arrivals and departures is challenging since each individual flow experiences independent wireless fading and thus, flows cannot be served in a strict round-robin manner. In this paper, we overcome this difficulty by exploring the intricate dynamics of TSLS-based algorithm and show that flows are provided round-robin-like service with a very high probability. Consequently, we then show that our algorithm can achieve throughput-optimality. Moreover, through simulations, we demonstrate that the proposed TSLS-based algorithm also exhibits desired properties such as delay-insensitivity and excellent short-term fairness performance in the presence of dynamic flows over wireless fading channels.

Original languageEnglish (US)
Title of host publicationMobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PublisherAssociation for Computing Machinery
Pages231-240
Number of pages10
ISBN (Electronic)9781450380157
DOIs
StatePublished - Oct 11 2020
Externally publishedYes
Event21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020 - Virtual, Online, United States
Duration: Oct 11 2020Oct 14 2020

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

Conference21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020
CountryUnited States
CityVirtual, Online
Period10/11/2010/14/20

Keywords

  • delay-insensitivity
  • flow-level dynamics
  • short-term fairness
  • throughout-optimality
  • wireless scheduling

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Emulating round-robin for serving dynamic flows over wireless fading channels'. Together they form a unique fingerprint.

Cite this